Edit Distance

Given two words word1 _and _word2 , find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example: Given word1 ="mart"and word2 ="karma", return3.

乍看之下可以用 dfs 遞迴去找，但是一但自很大就爆炸了

這種求 minimum 又是 string，很直覺可以用 dp 做，那麼就要想一下 dp 的方程該怎麼寫

我們可以定義 f[i][j] 表示 word1(0~i-1) 變成 word2(0~j-1) 所需要的最小次數

對於 word1, f[i][0] 表示 word1(0~i-1) 變為自己的距離，也就是 i

對於 word1, f[0][j] 表示 word2(0~j-1) 變為自己的距離，也就是 j

然後我們遍歷矩陣，對於 word1 == word2 的地方，我們就把 cost 設為 f[i-1][j-1]，

因為當前位置都一樣表示不需要做任何編輯，那麼就沿用 f[i-1][j-1]

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    char[] c1 = word1.toCharArray();
    char[] c2 = word2.toCharArray();
    int f[][] = new int[m+1][n+1];
    f[0][0] = 0; 
    for (int i=1; i<=m; i++) f[i][0] = i;
    for (int i=1; i<=n; i++) f[0][i] = i;

    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            if (c1[i-1] == c2[j-1]) {
                f[i][j] = f[i-1][j-1];
            } else {
                f[i][j] = 1 + Math.min(f[i-1][j-1], Math.min(f[i-1][j], f[i][j-1]));
            }
        }
    }
    return f[m][n];
}

逆反法:

會讓我寫不出來的原因:

• c1[i-1] == c2[j-1] 的 cost
• f[i][0], f[0][j] 初始