『パズルで鍛えるアルゴリズム力』の第3章で紹介されている「編集距離」をPythonで取り組んでみました。
3_3_edit_distance_solver.py
実行
% python 3_3_edit_distance_solver.py First String: ROOF Second String: SOFT ↘︎ ↘︎ ↓ ↘︎ → 3
文字列ROOFとSOFTの編集距離は3
RをSへ置換(1手目)、Oはそのまま、2個目のOを削除(2手目)、Fはそのまま、Tを挿入(3手目)
% python 3_3_edit_distance_solver.py First String: LOGISTIC Second String: ALGORITHM → ↘︎ → ↘︎ ↘︎ ↘︎ ↓ ↘︎ ↘︎ ↘︎ 6
文字列LOGISTICとALGORITHMの編集距離は6
Aを挿入(1手目)、Lはそのまま、Gを挿入(2手目)、Oはそのまま、GをLに置換(3手目)、Iはそのまま、Sを削除(4手目)、Tはそのまま、IをHに置換(5手目)、CをMに置換(6手目)
