解説 編集距離DPという典型を用います。 文字列SaS_aSaの先頭iii文字と、文字列SbS_bSbの先頭jjj文字を一致させるための操作コストをdp[i][j]dp[i][j]dp[i][j]とすると、dp[∣Sa∣][∣Sb∣]dp[|S_a|][|S_b|]dp[∣Sa∣][∣Sb∣]は、O(∣Sa∣∣Sb∣)O(|S_a||S_b|)O(∣Sa∣∣Sb∣)で漸化的に求めることができます。 ユーザー解説ユーザー解説を書くユーザー解説はまだありません。