Namaran

Code daily. Without assist.

2026-10-25

EditDistance.hs

editDistance :: String -> String -> Int

1文字の挿入・削除・置換をそれぞれ1回の操作と数え、文字列 a を b に変えるのに要る最小の操作回数を、a と b のレーベンシュタイン距離(Levenshtein distance)といいます。これを返す editDistance を書いてください。片方が空なら、距離はもう一方の長さです。a と b の長さを m と n として、計算量は O(m × n) に収めます。

入力例 1

editDistance "kitten" "sitting"

出力例 1

3

入力例 2

editDistance "flaw" "lawn"

出力例 2

2

入力例 3

editDistance "" "abc"

出力例 3

3
Reference
editDistance :: String -> String -> Int
editDistance a b = last (foldl' step [0 .. length a] (zip [1 ..] b))
 where
  step prev (i, c) = scanl (cell c) i (zip3 a prev (drop 1 prev))
  cell c left (x, diag, up) = minimum [up + 1, left + 1, diag + fromEnum (x /= c)]

b の先頭 i 文字と a の先頭 j 文字の距離を d(i, j) とすると、d(i, j) は d(i-1, j) + 1(上)、d(i, j-1) + 1(左)、d(i-1, j-1) に2つの文字が違えば1を足したもの(斜め)の最小です。これを表の行ごとに埋めていく解き方を動的計画法(dynamic programming)といいます。素直に再帰で書くと同じ d(i, j) を何度も計算し直し、時間は長さに対して指数的に増えます。ある行を作るのに要るのは1つ前の行だけなので、行を順に作り替えていけば O(m × n) で済みます。

最初の行は a の先頭 j 文字を空文字列に変える回数で、[0 .. length a] です。foldl' は b の文字を1つずつ見て、前の行 prev から次の行を作ります。zip3 a prev (drop 1 prev) は、列 j ごとに a の j 文字目、斜めの値 d(i-1, j-1)、上の値 d(i-1, j) を組にした列です。左の値は同じ行のすぐ前で計算したばかりの値なので、scanl が受け持ちます。scanl は直前に作った値を次の計算に渡しながら途中の値をすべて並べるので、その出力がそのまま新しい行になります。行の先頭は空文字列を b の先頭 i 文字に変える回数 i で、scanl の初期値にあたります。

最後の行の最後の要素が d(n, m) です。b が空なら畳み込みは1度も進まず、最初の行の最後の length a が返ります。a が空なら各行は [i] だけになり、最後に length b が残ります。掲載したのは参考実装で、唯一の正解ではありません。Data.Array で表全体を遅延評価の配列として定義し、各要素がほかの要素を参照する形で書いても、同じ計算量になります。1

  1. foldl' は、Haskell 2010 の報告書では Data.List から import する関数です。GHC 9.10 以降の base では Prelude からも export されているので、ここでは import を書いていません(書くと未使用の import として警告されます)。