# 72 Edit Distance

input: 兩個字串

output: 要經過幾個步驟才能將str1轉換成str2

可執行的動作包括：insert, remove, replace

以此兩字串為例

sunday
saturday

insert: saunday
insert: satunday
replace: saturday

三個步驟可將sunday轉換成saturday。

Concept

如何將此問題拆解成subproblem? 以此例來看，sunday -> saturday其實可以拆解成un -> atur 再拆解 un->atur是三步，其中兩步是un->atu，最後再補上一個r所以總共三步 由此可知，這兩個string的轉換，其實是由多個substring的轉換這些subproblem組合起來。 這種將問題拆解成subproblem的思路都可以用dp來解決。

所以就建立一個dp[m+1][n+1]的矩陣， 用來存str1(0,i)轉換成str2(0,j)所需要的步數。

可以執行的動作有 insert remove replace

insert: 從str1(0,i)變成str2(0,j)可表示為

dp[i+1][j+1] = dp[i+1][j]+1

remove: 從word(0,i)變成word(0,j)可表示為

dp[i+1][j+1] = dp[i][j+1]+1

replace: 從word(0,i)變成word(0,j)可表示為

dp[i+1][j+1] = str1.charAt(i) == str2.charAt(j)?dp[i][j]+1:dp[i][j]

對每個dp[i][j]都有上面三種選擇，選出三種選擇中結果最小的填入。

最後答案就是dp[m][n]。

code

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        //initialize dp
        for(int i=0; i<=m; i++){
            dp[i][0] = i;
        }
        for(int i=0; i<=n; i++){
            dp[0][i] = i;
        }

        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                dp[i][j] = word1.charAt(i-1) != word2.charAt(j-1) ? dp[i-1][j-1]+1:dp[i-1][j-1];
                dp[i][j] = Math.min(dp[i][j-1]+1 , Math.min(dp[i-1][j]+1,dp[i][j]));
            }
        }

        return dp[m][n];
    }
}