文字列の編集距離が1かどうかを効率的に確認する方法

プログラムを書いていると、2つの文字列がどれくらい似ているかを判断する必要に迫られることがあります。その一つの指標となるのが"編集距離"です。 今回は、2つの文字列の編集距離が1かどうかを効率的に判定する方法について解説します。

編集距離とは何か？

編集距離とは、ある文字列を別の文字列に変換するために必要な編集操作の最小回数のことです。 編集操作には、文字の挿入、削除、置換が含まれます。

• 挿入: 文字列に文字を追加する。
• 削除: 文字列から文字を削除する。
• 置換: 文字列中の文字を別の文字に置き換える。

編集距離1とは？

編集距離が1とは、上記の編集操作のいずれか1回のみで、ある文字列を別の文字列に変換できるということです。

例えば、"geeks"と"geek"は、's'を削除するだけで変換できるので、編集距離は1です。

編集距離1を判定する効率的なアルゴリズム

動的計画法(DP)を使うとO(n^2)で編集距離を計算できますが、もっと効率の良いO(m+n)のアルゴリズムがあります。ここでmとnはそれぞれ文字列s1とs2の長さです。以下はそのアルゴリズムの概要です。

1. 長さの差を確認: 2つの文字列の長さの差が1より大きい場合、編集距離は1を超えるため、偽(false)を返します。
2. 編集回数の初期化: 編集回数を表すcount変数を0に初期化します。
3. 同時走査: 2つの文字列を先頭から順に比較します。
   • 不一致の場合:
     • countをインクリメントします。
     • countが2以上になったら、偽(false)を返します。
     • 長さが異なる場合は、長い方の文字列のインデックスを進めます（挿入または削除に対応）。
     • 長さが同じ場合は，両方の文字列のインデックスを進めます（置換に対応）。
   • 一致する場合: 両方の文字列のインデックスを進めます。
4. 残りの文字の確認: どちらかの文字列に残りの文字がある場合、countをインクリメントします (最後の文字の挿入または削除に対応)。
5. 編集距離の判定: countが1であれば真(true)、そうでなければ偽(false)を返します。

コード例（C++）

#include <iostream>
#include <string>

using namespace std;

bool isEditDistanceOne(string s1, string s2) {
  int m = s1.length(), n = s2.length();
  if (abs(m - n) > 1) return false;

  int count = 0;
  int i = 0, j = 0;
  while (i < m && j < n) {
    if (s1[i] != s2[j]) {
      if (count == 1) return false;
      if (m > n) i++;
      else if (m < n) j++;
      else {
        i++;
        j++;
      }
      count++;
    } else {
      i++;
      j++;
    }
  }

  if (i < m || j < n) count++;
  return count == 1;
}

int main() {
  string s1 = "gfg";
  string s2 = "gf";
  if (isEditDistanceOne(s1, s2))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

各言語での実装例

上記のアルゴリズムは様々なプログラミング言語で実装できます。 記事にはC++, Java, Python, C#, Javascriptでの実装例が記載されているので、参考にしてみてください。

まとめ

今回は2つの文字列の編集距離が1かどうかを判定する方法について解説しました。 このアルゴリズムは、文字列の比較、スペルチェック、データ修正など、様々な場面で活用できます。 効率的なアルゴリズムを使用することで、パフォーマンスを向上させることができます。