どの編集操作を一回と数えるか
ここでは文字の挿入、削除、置換をそれぞれ費用1とするLevenshtein距離を考えます。同じ文字を対応させる費用は0です。隣接二文字の交換を一回とする操作は含めず、それを許す距離とは区別します。文字列の類似度を測る方法はほかにもありますが、許した操作と費用が変われば答えも変わります。例えばabからbaへは置換二回で費用2であり、交換一回の費用1ではありません。最短の編集回数が小さいことと、意味が近いことは同じではありません。
接頭辞の表へ分解する
D[i][j]を先頭i文字から先頭j文字へ変える最小費用とします。空文字列との境界はD[i][0]=i、D[0][j]=jです。内部では、削除D[i−1][j]+1、挿入D[i][j−1]+1、対応D[i−1][j−1]+cの最小を取り、cは二文字が同じなら0、違えば1です。各候補は最後に行った操作の違いなので、可能な編集列を漏らさず短い接頭辞の答えへ結びつけられます。表を埋める順番では、参照する上、左、左上のセルが既に計算済みである必要があります。
kittenからsittingへ変える
kittenの先頭kをsへ置換してsitten、eをiへ置換してsittin、末尾へgを挿入してsittingとすれば費用3です。動的計画法でもこの最小値を求められます。末尾だけを眺めて差を数えるのではなく、一文字の挿入で以後の対応位置がずれる可能性を表で扱います。実際の編集列が必要なら、各セルで選んだ前のセルへ最終位置から戻ります。同じ最小値を与える候補が複数ある場合には、複数の最適な編集列が存在することもあります。
領域削減と文字の仕様
長さmとnの全表は時間O(mn)、領域O(mn)です。距離の値だけなら直前行と現在行を保持してO(min(m,n))領域へ減らせますが、そのままでは全編集列の復元情報は残りません。費用の対称性を仮定して行と列を交換する場合も、操作費用が異なる版へ安易に広げないでください。Unicodeではコードポイントが同じ見た目の文字単位とは限らず、正規化の有無でも距離は変わります。空文字列、同一文字列、挿入だけの例、交換を一回と誤認しやすい例で仕様を検証します。