Pythonで2つの文字列が0または1の編集距離にあるかどうかを判定する方法

2つの文字列 S と T が与えられたとき、それらが「編集距離0（完全に一致）」または「編集距離1」の関係にあるかどうかを判定する問題を考えてみましょう。ここでいう編集操作とは、文字の削除、文字の追加、文字の置換の3種類を指します。

例えば、S = "hello"、T = "hallo" の場合、1文字だけ異なるため編集距離は1となり、出力は True になります。一方、S = "abc"、T = "xyz" のように複数箇所の変更が必要な場合は False を返します。

アルゴリズムの考え方

この問題は、両方の文字列を先頭から同時に走査しながら、不一致が見つかった回数をカウントするというシンプルなアプローチで解けます。手順は以下の通りです。

• m を S の長さ、n を T の長さとし、ポインタ i = 0、j = 0、カウンタ count = 0 で初期化します。
• |m − n| > 1 の場合、編集距離が必ず2以上になるため、即座に False を返します。
• i < m かつ j < n の間、以下を繰り返します。
  • S[i] と T[j] が異なる場合：
    • すでに count が1なら、これ以上の編集は許されないため False を返します。
    • m < n の場合（T の方が長い＝挿入が起きている）、j を1進めます。
    • m > n の場合（S の方が長い＝削除が起きている）、i を1進めます。
    • 長さが同じ場合（置換が起きている）、i と j を両方1進めます。
    • count を1増やします。
  • S[i] と T[j] が同じ場合：i と j を両方1進めます。
• ループを抜けたら True を返します。

実装例

以下がPythonでの実装コードです。

class Solution:
    def solve(self, S, T):
        m, n = len(S), len(T)
        i, j = 0, 0
        count = 0
        if abs(m - n) > 1:
            return False
        while i < m and j < n:
            if S[i] != T[j]:
                if count == 1:
                    return False
                if m < n:
                    j += 1
                elif m > n:
                    i += 1
                else:
                    i += 1
                    j += 1
                count += 1
            else:
                i += 1
                j += 1
        return True

ob = Solution()
S = "hello"
T = "hallo"
print(ob.solve(S, T))

入力

"hello", "hallo"

出力

True

計算量について

このアルゴリズムは各文字列を最大1回ずつ走査するだけなので、時間計算量は O(m + n)、空間計算量は O(1) と非常に効率的です。LeetCodeの「One Edit Distance」などの類似問題にもそのまま応用できる汎用的な手法なので、ぜひ覚えておきましょう。