動的計画法で 2 つの単語の編集距離を求める｜コーディング面接問題

問題

検索窓の打ち間違いを直す「もしかして」の機能を作っています。打たれた単語 src を、辞書の単語 dst に変えたいとき、次の 3 つの操作を合わせて最も少なくて何回で済むかを返す関数を書いてください。

どこかに 1 文字を挿入する
どこかの 1 文字を削除する
どこかの 1 文字を別の文字に置き換える

条件は次の通りです。

操作はどれも 1 回と数えます。3 つの操作を好きな順に、何回でも混ぜて使えます
src と dst の長さは、どちらも 0 以上 500 以下です。空の文字列も来ます
文字は英小文字だけです

入力と出力の例

例 1

先頭の s を削除し、p を m に置き換えれば 2 回です。

入力

src = "spoon"
dst = "moon"

出力

例 2

前から 1 文字ずつ置き換えると 5 回かかります。先頭の s を削除し、末尾に s を挿入すれば 2 回で済みます。

入力

src = "stone"
dst = "tones"

出力

例 3

空の文字列からは、全部の文字を挿入するしかありません。

入力

src = ""
dst = "web"

出力

面接での聞かれ方

面接では、短い一文で渡されたあと、計算量を詰める問いが続きます。

「2 つの文字列を、挿入、削除、置き換えで同じにする最小の手数を返してください」
書き終えると「表の記憶を減らせますか？」と聞かれます。2 次元の表から 1 行分へ縮められるかが、シニアとして見られるところです
「どの操作をしたかも返せますか？」「置き換えだけ 2 回と数えたら？」と、表の中身を変える問いが続くこともあります

文字ごとに左から合わせていく欲張りは、例 2 のように外れます。表の 1 つの欄が何を表すかを、書く前に言葉で決めておきます。

アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。

まず考える手順

段 1

まずは素直に、全部の手を試す再帰を考えます。2 つの単語の最後の文字を見て、同じなら両方を 1 文字ずつ縮め、違うなら「置き換え」「削除」「挿入」の 3 通りを全部試して小さいほうを取ります。正しい答えは出ますが、1 回ごとに 3 つに分かれるので、時間は最悪で O(3^(m + n)) ほどに増えます (m と n は 2 つの長さ)。しかも、同じ「前から i 文字と前から j 文字」の組を、違う道から何度も解き直しています。そこで、この組ごとの答えを表に覚えます。

段 2

最後の文字に注目します。src の前から i 文字と、dst の前から j 文字をそろえる最小の手数を d[i][j] と書きます。2 つの最後の文字が同じなら、何もせず d[i-1][j-1] です。違うなら、最後の操作は次の 3 通りのどれかです。

src の最後の文字を置き換えた。d[i-1][j-1] に 1 を足す
src の最後の文字を削除した。d[i-1][j] に 1 を足す
dst の最後の文字を挿入した。d[i][j-1] に 1 を足す

この 3 つの小さいほうが d[i][j] です。

段 3

表の端を決めます。d[0][j] は空から j 文字を作るので j 回の挿入、d[i][0] は i 文字を全部消すので i 回の削除です。あとは i を 0 から順に、各行で j を左から埋めれば、使う欄はいつも先に埋まっています。答えは右下の d[m][n] です。

例 1 の spoon から moon の表は次の通りです。行が src の前から i 文字、列が dst の前から j 文字です。

	空	m	o	o	n
空	0	1	2	3	4
s	1	1	2	3	4
p	2	2	2	3	4
o	3	3	2	2	3
o	4	4	3	2	3
n	5	5	4	3	2

右下の 2 が答えです。たとえば、上から 1 つ目の o の行 (spo) と、左から 1 つ目の o の列 (mo) が交わる欄は、spo を mo にする手数です。最後の文字が o どうしで同じなので、左上の欄 (sp を m にする手数) の 2 をそのまま写しています。

段 4

表全体は (m + 1) × (n + 1) の欄で、500 文字どうしなら 25 万欄ほどです。ただ、1 つの欄に要るのは「上」「左」「左上」の 3 つだけで、上と左上は 1 つ前の行にあります。そこで 1 行分の並び row だけを持ち、左から上書きしていきます。上書きすると左上の値が消えるので、上書きの前に diag という変数へ退かしておきます。

段 5

似た問いとのつながりも言えるようにしておきます。この最小の手数は、レーベンシュタイン距離とも呼ばれます。置き換えを使わず、挿入と削除だけで変えるなら、手数は「2 つの長さの和から、共通する最長の部分列の長さの 2 倍を引いた数」になります。spoon と moon なら共通する部分列 oon が 3 文字なので、5 + 4 - 6 = 3 回です。共通する部分列の求め方は2 つの文字列に共通する最長の部分列を求める問いにあります。

解答

Python

def edit_distance(src, dst):
    n = len(dst)
    row = list(range(n + 1))
    for i, a in enumerate(src):
        diag = row[0]
        row[0] = i + 1
        for j in range(n):
            up = row[j + 1]
            left = row[j]
            c = diag
            if a != dst[j]:
                c += 1
            c = min(c, up + 1)
            c = min(c, left + 1)
            row[j + 1] = c
            diag = up
    return row[n]

JavaScript

function editDistance(
  src, dst
) {
  const n = dst.length;
  const row = Array.from(
    { length: n + 1 },
    (_, j) => j,
  );
  let i = 0;
  for (const a of src) {
    i++;
    let diag = row[0];
    row[0] = i;
    let j = 0;
    for (const b of dst) {
      const up = row[j + 1];
      const left = row[j];
      let c = diag;
      if (a !== b) c++;
      c = Math.min(c, up + 1);
      c = Math.min(c, left + 1);
      row[j + 1] = c;
      diag = up;
      j++;
    }
  }
  return row[n];
}

Go

func editDistance(
	src, dst string,
) int {
	m, n := len(src), len(dst)
	row := make([]int, n+1)
	for j := range row {
		row[j] = j
	}
	for i := 0; i < m; i++ {
		diag := row[0]
		row[0] = i + 1
		for j := 0; j < n; j++ {
			up := row[j+1]
			left := row[j]
			c := diag
			if src[i] != dst[j] {
				c++
			}
			c = min(c, up+1)
			c = min(c, left+1)
			row[j+1] = c
			diag = up
		}
	}
	return row[n]
}

row[j + 1] を上書きする直前の値が「上」、すでに上書きした row[j] が「左」、diag が「左上」です。c は最初に「そのまま」か「置き換え」の手数を入れ、そのあと削除 (上から 1 足す) と挿入 (左から 1 足す) と比べて小さいほうを残します。文字は英小文字だけなので、Go は文字列を 1 バイトずつ比べています。

計算量

時間は O(m × n) です (m は src、n は dst の長さ)。表の欄を 1 つずつ、決まった回数の比べで埋めます。500 文字どうしなら 25 万欄です
使う記憶は O(n) です。1 行分の row と、変数がいくつかだけです
2 次元の表をそのまま持つ書き方は、時間は同じで記憶が O(m × n) です。短いほうの文字列を dst の側に回せば、記憶は O(min(m, n)) まで減らせます。手数は向きを入れ替えても変わりません (挿入と削除が入れ替わるだけ)

よくある間違い

左上の値を退かさずに上書きする。 1 行で書くとき、row[j] を上書きしたあとに次の欄で左上を読むと、もう今の行の値になっています。上書きの前に diag に取っておきます
表の端を 0 で埋める。 d[0][j] と d[i][0] は 0 ではなく j と i です。1 行で書くときも、行ごとに row[0] = i + 1 を書き換え忘れると、空の文字列の例で外れます
同じ文字でも 1 を足す。最後の文字が同じなら手数は増えません。置き換えの 1 は、文字が違うときだけ足します
前からそろえる欲張りで書く。例 2 の stone と tones を位置ごとに比べると 5 文字とも違いますが、答えは 2 です。ずれを直す削除と挿入を考えるために、表が要ります
再帰とメモで書いて深さを見落とす。 500 文字どうしだと、再帰の深さが 1000 段近くになり、Python の再帰の上限にかかります。表を下から埋める書き方の方が安全です

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

動的計画法で 2 つの単語の編集距離を求める

問題