Pythonで2つの文字列の編集距離がちょうど1であるかを判定する方法

2つの文字列 s と t が与えられたとき、両者の編集距離（エディット距離）がちょうど1であるかどうかを判定する問題を考えてみましょう。

ここでいう「編集距離」とは、一方の文字列をもう一方の文字列に変換するために必要な操作の回数のことです。許容される操作は次の3種類です。

• 1文字を挿入する
• 1文字を削除する
• 1文字を置き換える

例えば、s = "hello"、t = "heillo" の場合、s に「i」を1文字挿入するだけで t にできるため、出力は True になります。

アルゴリズムの考え方

この問題は、2つのポインタを使って両文字列を先頭から同時に走査することで、O(n) の計算量で効率的に解くことができます。手順は以下のとおりです。

1. |s の長さ − t の長さ| > 1 の場合は、編集距離が1になることはあり得ないため False を返します。
2. 編集回数をカウントする変数 edit_dist_cnt を 0 に初期化し、ポインタ i と j をそれぞれ 0 にします。
3. i < len(s) かつ j < len(t) の間、以下を繰り返します。
   • s[i] と t[j] が異なる場合：
     • すでに edit_dist_cnt が 1 なら、これ以上編集は許されないので False を返します。
     • s の方が長ければ i を進め（削除に相当）、t の方が長ければ j を進め（挿入に相当）、同じ長さなら両方進めます（置換に相当）。
     • edit_dist_cnt を 1 増やします。
   • s[i] と t[j] が一致する場合は、i と j を両方進めます。
4. ループ終了後、いずれかのポインタが末尾に達していない場合は、残りの文字分の編集が必要なので edit_dist_cnt を 1 増やします。
5. 最後に、edit_dist_cnt が 1 と等しければ True、そうでなければ False を返します。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(s, t):
    if abs(len(s) - len(t)) > 1:
        return False
    edit_dist_cnt = 0
    i = 0
    j = 0
    while i < len(s) and j < len(t):
        if s[i] != t[j]:
            if edit_dist_cnt == 1:
                return False
            if len(s) > len(t):
                i += 1
            elif len(s) < len(t):
                j += 1
            else:
                i += 1
                j += 1
            edit_dist_cnt += 1
        else:
            i += 1
            j += 1
    if i < len(s) or j < len(t):
        edit_dist_cnt += 1
    return edit_dist_cnt == 1

s = "hello"
t = "heillo"
print(solve(s, t))

入力

"hello", "heillo"

出力

True

計算量について

このアルゴリズムは各文字列を一度だけ走査するため、時間計算量は O(n)（n は長い方の文字列の長さ）、追加で必要なメモリは O(1) となります。一般的な動的計画法による編集距離計算（O(n×m)）と比べて非常に高速であり、「距離がちょうど1かどうか」という限定された条件を判定する場合には最適な手法です。