2026-11-06
edit_distance.cpp
int edit_distance(std::string_view a, std::string_view b) {
}
1文字の挿入、1文字の削除、1文字の置き換えをそれぞれ1回の操作と数え、文字列 a を b に変えるのに要る最小の操作回数を返す edit_distance を書いてください。どちらかが空なら、もう一方の長さが答えです。作業用の領域は、b.size() + 1 個の int を持つ配列1つだけにしてください。
入力例 1
edit_distance("kitten", "sitting")
出力例 1
3
入力例 2
edit_distance("flaw", "lawn")
出力例 2
2
入力例 3
edit_distance("", "abc")
出力例 3
3
Reference
Reference
int edit_distance(std::string_view a, std::string_view b) {
std::vector<int> row(b.size() + 1);
for (std::size_t j = 0; j <= b.size(); ++j) {
row[j] = j;
}
for (std::size_t i = 1; i <= a.size(); ++i) {
int diag = row[0];
row[0] = i;
for (std::size_t j = 1; j <= b.size(); ++j) {
int up = row[j];
row[j] = std::min({up + 1, row[j - 1] + 1, diag + (a[i - 1] != b[j - 1])});
diag = up;
}
}
return row[b.size()];
}
a の先頭 i 文字を b の先頭 j 文字に変える最小回数を D(i, j) とすると、最後の1文字をどう処理するかで3通りに分かれます。a の i 文字目を消すなら D(i − 1, j) + 1、b の j 文字目を足すなら D(i, j − 1) + 1、最後の文字どうしを対応させるなら D(i − 1, j − 1) に、文字が違うときだけ1を足した値です。D は1つ上の行と同じ行の左だけから決まるので、表全体を持たなくても、1行分の row を i ごとに上書きすれば足ります。row[j] は上書きする前は上の行の D(i − 1, j)、上書きしたあとは今の行の D(i, j) です。これは参考実装で、唯一の正解ではありません。
1行で済ませるときに失いやすいのが、左上の D(i − 1, j − 1) です。row[j - 1] はひとつ前の j で今の行の値に上書き済みなので、上の行の値はもう残っていません。参考実装は、上書きする直前の row[j] を up に取っておき、次の j に進む前に diag へ移しています。行の初めでは、row[0] を i に上書きする前に、上の行の row[0] を diag に入れます。取っておく順序を誤ると、置き換えの候補に今の行の値が混ざります。入力例3のように a が空なら外側のループは回らず、初期化した row[3] = 3 がそのまま答えになります。