問題と適用シナリオ
2つの文字列 source と target が与えられたとき、source を target に変換するために必要な最小編集回数を返します。1回の編集では、1文字の挿入、1文字の削除、または1文字の置換を行います。すべての操作のコストは 1です。どちらの文字列も空である可能性があり、両方とも英小文字のみを含みます。
source = "horse"
target = "ros"
horse -> rorse replace h with r
rorse -> rose delete r
rose -> ros delete e
answer = 3m = source.length かつ n = target.length とし、両方の長さは最大で2,000とします。この課題で求められているのは 最小コストのみであり、編集スクリプトではありません。Wagner–Fischerの論文では、文字列の修正を挿入、削除、置換の最小コストシーケンスとして定義し、実行時間が2つの長さの積に比例するアルゴリズムを提示しています。2026年現在の面接ガイドでも、編集距離は依然として2つの文字列に対する標準的な動的計画法（DP）の演習問題として用いられています。これはこのトピックの対策としての価値を裏付けるものであり、特定の企業の出題頻度や帰属を証明するものではありません。
この問題はスペルチェック、あいまい一致（ファジーマッチング）、レコード結合、シーケンス比較などに現れますが、実運用の定義では重み付き操作、転置、正規化、またはドメイン固有のトークンが使用されることがあります。面接版では、状態と証明を明確にするために、あえて単位コストの文字編集に固定されています。
面接官が見ているポイント
最初の評価基準は、厳密な境界を持つ状態の定義です。dp[i][j] を、source の最初の i 文字を target の最初の j 文字に変換するために必要な最小編集回数として定義します。「i と j までの答え」という表現は曖昧すぎて、遷移の正当化や空のプレフィックスの初期化を説明できません。
2つ目の評価基準は、文字が一致しない場合の3つの遷移をすべて導出できることです。最適解の最後の操作は、削除、挿入、置換のいずれか1つでなければなりません。その最後の操作を取り除くと、より小さいプレフィックスの問題が残ります。候補者は3つの座標を暗記するのではなく、各操作を正しい隣接セルに対応付ける必要があります。
3つ目の評価基準は、末尾の文字が一致する場合に余計な処理を挟まずに処理できることです。source[i - 1] が target[j - 1] と等しい場合、最適解はその文字を変更せずに維持できるため、値は dp[i - 1][j - 1] からそのまま引き継がれます。証明では、この選択によってよりコストの低い解が見落とされていないことも示す必要があります。
4つ目の評価基準は、依存関係の形状を認識することです。ある行の計算には前の行と自身の左のセルしか使用しないため、距離のみを返す場合には完全な O(mn) 行列は不要です。短い方の文字列を列の次元に配置することで、O(min(m, n)) の補助空間を実現できます。
最後の評価基準は、問題の制約契約を守ることです。行と列の文字列を入れ替えることは、単位コストの挿入と削除によって距離が対称になるため、ここでは有効です。しかし、挿入と削除の重みが異なる場合は自動的に有効とはなりません。また、Unicodeテキストでは、UTF-16コードユニット、Unicodeコードポイント、ユーザーが知覚する書記素クラスタ（grapheme cluster）のどれを基準にするかを明示的に選択する必要があります。
回答前に明確にすべき質問
- どの操作が許可されていますか？ この問題では挿入、削除、置換が許可されています。隣接する文字の転置は1回の操作としては認められません。
- 1回の編集のコストはいくらですか？ 許可されているすべての操作のコストは1です。コストに重みがある場合、漸化式が変化し、対称性が失われる可能性があります。
- 比較の単位は何ですか？ 問題文では英小文字が使用されているため、この実装ではJavaScriptのインデックス指定で安全です。一般的なUnicodeテキストには別の契約が必要です。
- 距離のみを返しますか、それとも編集スクリプトを返しますか？ 距離のみです。操作を復元する場合は、通常、完全なテーブルまたは明示的な遷移元の情報を保持します。
- 入力のいずれかが空になることはありますか？ はい。空文字列を長さ
jのプレフィックスに変換するには正確にj回の挿入が必要であり、その逆はi回の削除が必要です。 - サイズの制限はどのくらいですか？ 長さが最大2,000であるため、
O(mn)時間は許容されますが、指数関数的な再帰や不要なテーブル全体のメモリ確保は避けるべきです。 - メモリ節約のために入力を入れ替えることはできますか？ はい、距離が対称であるこの単位コストの契約下では可能です。それを使用する前にその前提を述べてください。
30秒回答フレームワーク
「dp[i][j] を、source の最初の i 文字から target の最初の j 文字への変換に必要な最小編集回数として定義します。空プレフィックスのコストで最初の行と列を初期化します。末尾の文字が等しい場合は、対角線の値をそのまま使用します。それ以外の場合、最後の編集は削除、挿入、置換のいずれかであるため、上、左、対角線のセルの最小値に1を加えます。各セルは前の行と現在の行の左の値にのみ依存するため、短い方の文字列を列に配置して2行のみを保持します。これにより、O(mn) 時間と O(min(m, n)) 空間が実現されます。空文字列、等しい文字列、長さが非対称な文字列、および小さな入力でのフルテーブル参照に対する結果を検証します。」
ステップごとの詳細解説
プレフィックスから始めます。dp[i][j] を、source[0..i - 1] を target[0..j - 1] に変換するために必要な許可された編集の最小回数とします。
空プレフィックスの境界条件は、契約から直接導かれます。
dp[0][j] = j // insert all j target characters
dp[i][0] = i // delete all i source characters空でないプレフィックスの場合は、末尾の文字を確認します。それらが一致する場合、その共通の末尾文字をそのまま維持することで、問題は2つのより短いプレフィックスに帰着します。
if source[i - 1] == target[j - 1]:
dp[i][j] = dp[i - 1][j - 1]異なる場合は、任意の最適手順における最後の編集を分類します。
delete source[i - 1]: dp[i - 1][j] + 1
insert target[j - 1]: dp[i][j - 1] + 1
replace the final character: dp[i - 1][j - 1] + 1
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])最後の操作は許可された3つの編集のいずれかでなければならないため、これらは網羅的です。また、これらは構成的です。選択されたより小さいプレフィックスに対する最適解に対象の編集を追加すると、(i, j) に対する有効な解が生成されます。逆に、任意の最適解から最後の編集を取り除くと、残りは対応するより小さいプレフィックスを解くことになるため、そのセルのコストを下回ることはできません。これにより、不一致時の漸化式が証明されます。
末尾の文字が一致する場合、それらを一致したまま残す最適解が存在します。ある最適手順が source または target の末尾文字を編集する場合、それらの最終的な効果を取り除き、代わりに等しい文字同士を整列させます。これによってコストが増加することはありません。残りの作業はまさに斜め方向のプレフィックスの問題となります。空プレフィックスの境界をベースとする i + j に対する帰納法により、すべてのセル、したがって dp[m][n] が証明されます。
行を埋める際に必要な過去の値は3つだけです。削除のための previous[j]、挿入のための current[j - 1]、置換または一致のための previous[j - 1] です。コードでは短い方の文字列を列にしています。この入れ替えは、この対称な単位コスト定義におけるメモリ最適化であり、答えを変えるものではありません。
export function editDistance(source: string, target: string): number {
const rows = source.length >= target.length ? source : target
const columns = source.length >= target.length ? target : source
let previous = Array.from(
{ length: columns.length + 1 },
(_, index) => index,
)
for (let row = 1; row <= rows.length; row += 1) {
const current = new Array<number>(columns.length + 1)
current[0] = row
for (let column = 1; column <= columns.length; column += 1) {
if (rows[row - 1] === columns[column - 1]) {
current[column] = previous[column - 1]
continue
}
const deleteCost = previous[column] + 1
const insertCost = current[column - 1] + 1
const replaceCost = previous[column - 1] + 1
current[column] = Math.min(deleteCost, insertCost, replaceCost)
}
previous = current
}
return previous[columns.length]
}source = "horse" と target = "ros" の場合、より短い列の次元の長さは3です。最後の行は3で終わり、これは置換に加えて2回の削除を行う手順と一致します。このアルゴリズムはコストを返すものであり、この特定の編集手順が一意であることを主張するものではありません。
計算量、境界条件、および設計上の選択
このアルゴリズムは (m + 1)(n + 1) 個の概念的な状態を埋めるため、時間は O(mn) です。各行には min(m, n) + 1 個の要素があり、同時に存在するのは2行だけであるため、補助空間は O(min(m, n)) です。反復ごとに行を再割り当てしても計算量の限界は変わりませんが、再利用可能な2つの配列を使用すると、アルゴリズムを変更することなく割り当ての負荷を軽減できます。
単位コストの挿入、削除、置換における最大値は max(m, n) です。最初の min(m, n) 文字を置換し、その後に長さの差分を挿入または削除します。最小値は少なくとも |m - n| です。各編集によって長さが高々1しか変化しないためです。これらの境界は、テストにおける有用なアサーションになります。
一般的なJavaScript文字列の場合、インデックスによるアクセスはUTF-16コードユニットに対して機能します。文字列の反復処理（イテレーション）はUnicodeコードポイントを生成することでサロゲートペアを保持しますが、絵文字に肌の色が付いたものやゼロ幅接合子（ZWJ）シーケンスなどの1つの書記素クラスタを分割してしまう可能性があります。実運用の類似度機能では、トークナイザーを選択する前に、編集をコードユニット、コードポイント、正規化された書記素クラスタ、単語、またはドメイン固有トークンのいずれに適用するかを決定する必要があります。暗黙的な正規化はプロダクトのセマンティクスを変更する可能性もあるため、このDPループ内ではなく契約で定義するべきです。
呼び出し側が距離が高々 k であるかどうかのみを問い合わせている場合は、まず |m - n| > k のときに棄却し、次に主対角線の周りの帯状の領域（バンド）のみを評価して、アクティブなバンド内のどの状態も k 以内に収まらなくなった時点で停止します。それは異なる出力契約であり、完全な距離を求める実装で投機的にそのような複雑さを追加するべきではありません。
質の高い模範解答
「プレフィックスを用いて問題をモデル化します。dp[i][j] を、source の最初の i 文字を target の最初の j 文字に変換するための最小コストとします。空プレフィックスの境界はその長さとなります。末尾の文字が等しい場合は、対角線の値を保持します。末尾の文字が異なる場合は、最後の編集によって最適シーケンスを分類します。削除は上のセルを使用し、挿入は左のセルを使用し、置換は対角線のセルを使用して、それらの最小値に1を加えます。これらのケースは網羅的であり、最後の編集を取り除くことで逆方向の漸化式も証明されます。
各セルは前の行と現在の行の左のセルのみを使用するため、2つの行を保持します。単位コストの挿入と削除によりこの距離は対称となるため、短い方の文字列を列にすることができ、メモリは O(min(m, n)) となり、時間は O(mn) のままです。非対称な重みの場合はこの入れ替えを行いません。空文字列の両方向、等しい文字列、horse から ros への例、およびランダム生成された短い文字列をフルテーブル版と比較してテストします。面接官が編集スクリプトを必要とする場合は、上書きされた行から復元できると約束するのではなく、遷移元の情報を保持します。」
よくある間違い
- 貪欲法（Greedy）による文字マッチングを使用する → 重複文字やその後のズレによって、局所的に都合の良い編集が全体の最小値を損なう → 最適なプレフィックス状態を定義し、すべての正当な最終操作を比較する。
- 最初の行と列を0で初期化する → 空文字列のケースのコストが無料になってしまう → 境界コストをそれぞれのプレフィックス長に設定する。
- 挿入と削除の隣接セルを取り違える → 対称な例は通過しても非対称なプレフィックスで失敗することがある → 最後の操作を取り除いた後にどの文字列が残るかを説明する。
- 末尾の文字が一致するときに1を加算する → 変更されていない等しい文字が置換として課金される → 一致時は対角線の値をそのままコピーする。
- 編集スクリプトを復元すると約束しながらローリング配列の結果を返す → 上書きされた遷移元情報からパスを再構築することはできない → 操作が必要な場合は行列またはバックポインタを保持する。
- 非対称な重みの下で文字列を入れ替える → 一方向の挿入が他方向の削除になってしまう → コストモデルが対称でない限り、元の向きを維持する。
- 任意のUnicodeに対してJavaScriptのインデックスを「文字」と呼ぶ → サロゲートペアや書記素クラスタが予期せずカウントされる → 比較単位を明示的に定義してトークン化する。
焦点を絞ったテストセットには、("", "") = 0、("", "abc") = 3、("abc", "") = 3、("same", "same") = 0、("aaaa", "aa") = 2、("horse", "ros") = 3、および ("intention", "execution") = 5 が含まれます。小さなアルファベットから生成されたすべての短い文字列に対して、ローリング実装をフルテーブルの参照実装と比較します。また、同一性、このコストモデル下での対称性、|m - n| ≤ d ≤ max(m, n)、および生成された3つ組に対する三角不等式を確認します。最後に、長さ2,000の同一入力および完全に異なる入力を実行して、極端なサイズでの実行パスが期待通りの2乗時間と線形空間内に収まることを確認します。
面接でのフォローアップ質問
フォローアップ1：実際の編集操作を返すにはどうすればよいですか？
完全なテーブルを保持し、(m, n) からバックトラックします。一致した場合は操作を出力せずに対角線上に移動します。それ以外の場合は、その値に対応する編集コストを加えたものが現在の値と等しくなる隣接セルを選択します。複数の最小手順が存在する可能性があるため、安定したタイブレークルールを定義します。直接的な方法では O(mn) の空間を使用します。分割統治法を用いれば線形空間での再構築も可能ですが、それは別のアルゴリズムであり、メモリ要件から要求された場合にのみ導入するべきです。
フォローアップ2：操作に異なる重みがある場合は何が変わりますか？
1の代わりに、関連する重みを各遷移に加えます。コストが非負であり契約によって定義されている場合、同じ部分構造最適性の証明が機能します。挿入と削除のコストが異なる場合、距離に方向性が生じる可能性があるため、行を短くするために文字列を入れ替えることは自動的には正しくなくなります。負の編集コストは通常の解釈を破綻させるため、モデルの再検討が必要です。
フォローアップ3：隣接する文字の転置をサポートするにはどうすればよいですか？
まず、転置が隣接する文字のみを入れ替えるのか、また重複する転置が許可されるのかを明確にします。制限付きの最適文字列アライメントの漸化式では、さらに前の2文字と、2行2列前のセルを調べることができます。完全なダメラウ・レーベンシュタイン距離には異なる状態要件があります。単に非公式な対角線チェックを1つ追加するだけでは、誤ったバリアントを実装してしまう可能性があります。
フォローアップ4：最長共通部分列（LCS）との関係は何ですか？
置換が禁止されているか、または1回の削除＋1回の挿入と同じコストである場合、挿入と削除の距離は LCS から m + n - 2 * LCS(source, target) として導出できます。単位コストの置換がある場合、その式は一般には編集距離になりません。一致しない1文字を置換するコストは1ですが、削除＋挿入のコストは2になるためです。この関係を使用する前に操作コストを明示してください。
フォローアップ5：「距離は高々kか？」により速く答えるにはどうすればよいですか？
長さの差が k を超える場合は、直ちに false を返します。それ以外の場合は、主対角線から k 以内の状態のみを計算し、帯の外側のセルを到達不能として扱い、アクティブなフロンティアが予算内に戻れなくなった場合は停止します。これにより、k が小さい場合に作業を大幅に削減できますが、制限のない距離計算の最悪ケースは依然として2乗のままです。
フォローアップ6：実際にユーザーに見えるUnicodeテキストをどのように処理しますか？
プロダクトオーナーと単位を選択します。コードポイントによる反復処理はサロゲートペアの分割を防ぎますが、ユーザーが知覚する一部の文字は依然として分割されます。書記素セグメンテーションは目に見える文字により良く一致し、Unicode正規化によって正規等価なシーケンスを一貫して比較できるようになります。ロケール、ケースフォールディング、アクセント、およびトークンレベルのルールはプロダクトの決定事項です。DPの前にその前処理を適用し、サポート対象言語の例でテストします。
フォローアップ7：1つの行で2つの行を置き換えることはできますか？
はい。dp[j] を上書きする前に、その古い値を次の対角線の値として保存します。dp[j] は引き続き上のセルを表し、dp[j - 1] はすでに現在の行の左のセルを表しています。これにより定数倍のオーバーヘッドが削減されますが、漸近的な空間量は変わりません。面接では、面接官がインプレース変形を明示的に要求しない限り、2行を用いる方が証明しやすく、ミスも少なくなります。