ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.225 文字列変更(medium)

DP★3.レーベンシュタイン距離の実装問題.スペルチェッカーなどに使うのだそう.

参考:

レーベンシュタイン距離 - Wikipedia

No.225 文字列変更(medium) - yukicoder

解答:愚直に実装しました.DP用マトリクスを作って順に埋めていく感じがわかりやすくていいですね.

似たようなアルゴリズムにDTWを連想しました.これに関しても何か面白い問題がありそう.

Dynamic time warping - Wikipedia, the free encyclopedia

yukicoder No.225