編集距離（Levenshtein距離）
挿入・削除・置換操作に対する編集距離の漸化式を導き、長さの異なる文字列の組み合わせについてDPテーブルを埋めます。
「編集距離（Levenshtein距離）」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
編集距離の問題
編集距離（レーベンシュタイン距離、LeetCode 72）では、ある文字列を別の文字列に変換するために必要な挿入、削除、置換の操作回数の最小値を求めます。たとえば、'horse'を'ros'に変換するには、'h'→'r'を置換（horse→rorse）、'r'を削除（rorse→rose）、'e'を削除（rose→ros）するため、3回の操作が必要です。編集距離は、スペルチェッカー、DNAアラインメント、あいまいマッチングの基礎となっています。
# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)
# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose (delete r at index 1)
# 3. rose → ros (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')DPの状態と漸化式
dp[i][j]を、word1[:i]とword2[:j]の間の最小編集距離と定義します。word1[i-1] == word2[j-1]の場合は操作が不要なので、dp[i][j] = dp[i-1][j-1]です。それ以外の場合は、3つの操作の最小値を取ります。挿入はdp[i][j-1] + 1、削除はdp[i-1][j] + 1、置換はdp[i-1][j-1] + 1です。基本ケースは、dp[i][0] = i（word1をすべて削除）とdp[0][j] = j（word2をすべて挿入）です。
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
# Base cases
for i in range(m+1): dp[i][0] = i # delete all of word1
for j in range(n+1): dp[0][j] = j # insert all of word2
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # no cost
else:
dp[i][j] = 1 + min(
dp[i][j-1], # insert
dp[i-1][j], # delete
dp[i-1][j-1] # replace
)
return dp[m][n]
print(edit_distance('horse', 'ros')) # 3
print(edit_distance('intention', 'execution')) # 53つの操作を理解する
3つの操作は、DPテーブル上の移動に直接対応しています。置換 dp[i-1][j-1]+1 — 両方の文字を対応させますが、コストを1支払います。word1からの削除 dp[i-1][j]+1 — word1から文字を削除します（テーブル上で上に移動）。word1への挿入 dp[i][j-1]+1 — word2の文字に対応する文字を挿入します（左に移動）。3つの値の最小値が最適な編集経路を与えます。
# Visualise the DP table for 'cat' → 'cut'
# dp[i][j] = min edits for word1[:i] vs word2[:j]
word1, word2 = 'cat', 'cut'
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
print(' ', ' '.join(' '+word2))
for i, row in enumerate(dp):
print((' ' if i==0 else word1[i-1]), row)O(n)への空間最適化
編集距離で必要なのは、現在の行と直前の行だけです。サイズがn+1の1次元配列を使用し、各セルを更新する前にdiagonalの値（dp[i-1][j-1]）を別に保持します。左から右へ処理します。temp = dp[j]（古い値はdp[i-1][j]）として保存し、dp[j]（削除）、dp[j-1]（挿入）、diagonal（置換）を使ってdp[j]を更新します。
def edit_distance_1d(word1, word2):
m, n = len(word1), len(word2)
dp = list(range(n + 1)) # initial row: 0,1,2,...,n
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j] before overwrite
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], # delete
dp[j-1], # insert
diag) # replace
diag = temp
return dp[n]
print(edit_distance_1d('horse', 'ros')) # 3
print(edit_distance_1d('intention', 'execution')) # 5編集操作の復元
実際の編集系列を復元するには、(m, n)からDPテーブルをバックトラックします。各セルで、word1[i-1] == word2[j-1]の場合は斜めに移動します（操作なし）。それ以外の場合は、3つの隣接セルのうち最小値を与えたものを特定し、対応する操作を記録します。これにより編集スクリプトが逆順に得られるため、最終的な答えでは反転します。
def edit_ops(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0]=i
for j in range(n+1): dp[0][j]=j
for i in range(1,m+1):
for j in range(1,n+1):
if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
ops, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and word1[i-1]==word2[j-1]:
i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]<=dp[i-1][j] and dp[i][j-1]<=dp[i-1][j-1]):
ops.append(f'Insert {word2[j-1]} at pos {i}'); j-=1
elif i>0 and (j==0 or dp[i-1][j]<=dp[i][j-1] and dp[i-1][j]<=dp[i-1][j-1]):
ops.append(f'Delete {word1[i-1]} at pos {i-1}'); i-=1
else:
ops.append(f'Replace {word1[i-1]} with {word2[j-1]}'); i-=1; j-=1
return list(reversed(ops))
for op in edit_ops('horse', 'ros'): print(op)1回の編集距離の判定
面接でよく出る、より簡単な問題として、2つの文字列がちょうど1回の編集操作分だけ異なるかを判定するものがあります。これはDPを使わずにO(n)で解けます。両方の文字列を同時に走査します。不一致が見つかったら、3つの操作（s1の文字を1つスキップ、s2の文字を1つスキップ、両方を1つずつスキップ）をすべて試し、残りの部分が同一か確認します。不一致が2回発生したらFalseを返します。距離が1以下かどうかだけを知りたい場合、この貪欲法によって完全なO(mn) DPを避けられます。
def is_one_edit_distance(s, t):
m, n = len(s), len(t)
if abs(m - n) > 1: return False
if m > n: return is_one_edit_distance(t, s) # ensure m <= n
for i in range(m):
if s[i] != t[i]:
if m == n:
return s[i+1:] == t[i+1:] # replace
else:
return s[i:] == t[i+1:] # insert into s (delete from t)
return m + 1 == n # all matched, lengths differ by 1
print(is_one_edit_distance('ab', 'acb')) # True (insert c)
print(is_one_edit_distance('ab', 'ab')) # False (zero edits)
print(is_one_edit_distance('ab', 'abc')) # True (append c)
print(is_one_edit_distance('ab', 'xyz')) # False編集距離とLCSの比較
すべての操作を許可した編集距離とLCSは、文字列の類似性を相補的に捉える方法です。編集距離は差異を数え、LCSは類似性を数えます。挿入と削除だけを許可し（置換は不可）、編集距離はm + n - 2×LCSとなります。置換を許可する場合、DPは少し異なります。一致時は対角方向の値dp[i-1][j-1]をそのまま使い（コスト0）、置換時はdp[i-1][j-1]+1を使います。どちらのアルゴリズムもO(mn)時間で実行されます。
def lcs_len(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
return dp[m][n]
def edit_insert_delete_only(s1, s2):
return len(s1) + len(s2) - 2 * lcs_len(s1, s2)
print(edit_insert_delete_only('sea', 'eat')) # 2
print(edit_distance('sea', 'eat')) # 2 (same here: replace not needed)あいまい文字列マッチング
編集距離は、実際のあいまいマッチングを支えています。スペルチェッカーは、入力された単語から編集距離1または2以内にある修正候補を提案します。大規模に処理する際の課題は、O(mn × dict_size)回の比較を避けることです。解決策には、BK木（編集距離用の距離木）、n-gramインデックス、Bitapのような近似文字列マッチングアルゴリズムがあります。基礎となるDPを理解すると、これらの高水準なツールの効率について考えやすくなります。
def spell_suggest(typed, dictionary, max_dist=2):
'''Return words in dictionary within max_dist edits of typed.'''
suggestions = []
for word in dictionary:
if abs(len(typed) - len(word)) <= max_dist:
if edit_distance(typed, word) <= max_dist:
suggestions.append(word)
return suggestions
def edit_distance(w1, w2):
dp = list(range(len(w2)+1))
for i,c1 in enumerate(w1,1):
prev = i
for j,c2 in enumerate(w2,1):
temp = dp[j]
dp[j] = prev if c1==c2 else 1+min(dp[j],prev,dp[j-1])
prev = temp
return dp[len(w2)]
dictionary = ['horse', 'worse', 'house', 'morse', 'nurse']
print(spell_suggest('harse', dictionary)) # horse, worse, house, morse重み付き編集距離
アプリケーションによっては、操作ごとに異なるコストを設定します。たとえば、隣接する文字の入れ替え（よくあるタイプミス）は、完全な置換よりも低いコストにする場合があります。Damerau-Levenshtein距離は、4つ目の操作として入れ替えを追加したものです。DPでは、word1[i-1]==word2[j-2]かつword1[i-2]==word2[j-1]の場合に、dp[i-2][j-2]+1も確認するよう拡張します。これにより、キーボード入力のタイプミスをより正確にモデル化できます。
def damerau_levenshtein(s, t):
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0]=i
for j in range(n+1): dp[0][j]=j
for i in range(1,m+1):
for j in range(1,n+1):
cost = 0 if s[i-1]==t[j-1] else 1
dp[i][j] = min(
dp[i-1][j]+1, # delete
dp[i][j-1]+1, # insert
dp[i-1][j-1]+cost # replace
)
# Transposition
if i>1 and j>1 and s[i-1]==t[j-2] and s[i-2]==t[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2]+1)
return dp[m][n]
print(damerau_levenshtein('CA', 'ABC')) # 2
print(damerau_levenshtein('ab', 'ba')) # 1 (transposition)DNA配列アラインメント
バイオインフォマティクスでは、DNA配列アラインメントに編集距離の派生手法を使用します。Needleman-Wunschアルゴリズムは、LCSや編集距離と密接に関係するグローバルアラインメントDPです。一致には+1、不一致には-1、ギャップ（挿入・削除）にはペナルティを与えます。Smith-Watermanの派生手法はローカルアラインメントを行います（最もよく一致する部分文字列を探します）。どちらも同じテーブル充填構造を持つO(mn)のDPアルゴリズムです。
def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-1):
m, n = len(seq1), len(seq2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i * gap
for j in range(n+1): dp[0][j] = j * gap
for i in range(1,m+1):
for j in range(1,n+1):
score = match if seq1[i-1]==seq2[j-1] else mismatch
dp[i][j] = max(
dp[i-1][j-1] + score, # align
dp[i-1][j] + gap, # gap in seq2
dp[i][j-1] + gap # gap in seq1
)
return dp[m][n]
print(needleman_wunsch('GATTACA', 'GCATGCU')) # alignment score編集距離に取り組む面接での方法
面接で編集距離を問われた場合は、次のように進めます。(1) 許可される操作（挿入・削除・置換）を確認します。(2) DPの状態を明確に定義します。(3) 3つのケースと漸化式を明示的に書き出します。(4) 基本ケースとしてdp[i][0]=iとdp[0][j]=jを示します。(5) O(n)空間への最適化に言及します。(6) 時間があれば、'cat'→'cut'（置換1回）のような小さな例をたどって検証します。標準的な計算量は、時間がO(mn)、空間がO(mn)からO(n)です。
# Clean interview solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
# O(n) space with rolling row
dp = list(range(n + 1))
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], dp[j-1], diag)
diag = temp
return dp[n]
# Time: O(mn), Space: O(n)
print(min_distance('horse', 'ros')) # 3
print(min_distance('intention', 'execution')) # 5
print(min_distance('', 'abc')) # 3
print(min_distance('abc', '')) # 3クイックチェック
このレッスンのData Structures & Algorithms — Coding Interview Prepに関する理解度を確認します。
レッスンのまとめ
このレッスンでは、編集距離 dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost) は、一致時のcost=0、それ以外では1となること、基本ケース dp[i][0]=i と dp[0][j]=j は、空文字列への変換または空文字列からの変換を表すこと、そしてO(n)空間への最適化では、diagonal変数を使ったローリング1次元配列を使用することを学びました。次は、同じローリング配列のテクニックを適用し、2D DPテーブルの空間をO(mn)からO(min(m,n))へ削減します。
よくある質問
「編集距離（Levenshtein距離）」レッスンは無料ですか？
はい。「編集距離（Levenshtein距離）」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「編集距離（Levenshtein距離）」で何を学びますか？
挿入・削除・置換操作に対する編集距離の漸化式を導き、長さの異なる文字列の組み合わせについてDPテーブルを埋めます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「編集距離（Levenshtein距離）」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- グリッド上のUnique Pathsと最小経路和
- 最長共通部分列
- 編集距離（Levenshtein距離）
- 2D DPの空間最適化