文字列の編集距離が1であるかを確認する方法：効率的なアルゴリズムと実装

この記事では、2つの文字列間の編集距離が1であるかどうかを効率よく判断する方法について解説します。編集距離とは、ある文字列を別の文字列に変換するために必要な最小の編集操作（挿入、削除、置換）の回数のことです。

編集距離とは？

編集距離は、2つの文字列がどれだけ似ているかを示す指標です。値が小さいほど、文字列は似ていると言えます。

• 編集操作の種類: 挿入、削除、置換などの操作が含まれます。
• 応用例: スペルチェック、DNA配列の比較、音声認識など、幅広い分野で利用されています。

編集距離1とは？

編集距離が1であるとは、2つの文字列が以下のいずれかの操作を1回行うことで一致することを意味します。

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

シンプルな解決策：動的計画法

動的計画法（DP）を用いて編集距離を計算し、その距離が1かどうかを判定する方法です。

• 仕組み: 2つの文字列のすべての部分文字列間の編集距離を計算し、テーブルに格納します。
• 時間計算量: O(n^2) (nは文字列の長さ)。
• 短所: 効率が悪く、大規模な文字列には不向きです。

効率的な解決策：線形時間アルゴリズム

文字列を同時に走査し、異なる文字の数をカウントする方法です。これにより、時間計算量をO(m+n) (m,nは各文字列の長さ)に短縮できます。

• アルゴリズム:
  1. 2つの文字列長を比較し、その差が1より大きい場合はfalseを返します。
  2. 異なる文字数をカウントする変数countを0で初期化します。
  3. 2つの文字列を先頭から文字ごとに比較します。
     • 文字が異なる場合、countをインクリメントします。
     • countが1より大きくなったらfalseを返します。
     • 文字列長が異なる場合は、長い方の文字列のインデックスを進めます。
     • 文字列長が同じ場合は、両方の文字列のインデックスを進めます。
     • 文字が同じ場合は、両方の文字列のインデックスを進めます。
  4. ループ終了後、countが1であればtrueを、そうでなければfalseを返します。

コード例 (C++)

#include <iostream>
#include <string>
#include <algorithm>

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";
  isEditDistanceOne(s1, s2) ? cout << "Yes" : cout << "No";
  return 0;
}

さまざまなプログラミング言語での実装

上記アルゴリズムは、C++, Java, Python3, C#, Javascriptなど、様々なプログラミング言語で実装可能です。記事には様々な言語でのコード例が掲載されています。

まとめ

文字列の編集距離が1であるかを判定する効率的な方法を解説しました。線形時間アルゴリズムを用いることで、大規模な文字列でも高速に判定できます。この記事で紹介したコード例を参考に、ぜひご自身のプロジェクトで活用してください。