LeetCode - Edit Distance

LeetCode - 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:

a) Insert a character
b) Delete a character
c) Replace a character

f(i-1, j-1) word1[i] == word2[j]

f(i, j) =

Min{ f(i-1, j), f(i, j-1), f(i-1, j-1} } + 1 word1[i] != word2[j]

如上所示，f(i, j)表示word1.substring(i)與word2.substring(j)直接的距離

1）顯然，如果word1[i] == word2[j]，轉化為遞歸解，即f(i-1, j-1)

2）如果word1[i] == word2[j]，則可以對兩個字符的最後一個字符串進行三種操作，對與字符word1[i]可以進行如下三種操作：

i) delete，即把此字符刪除，則問題轉化為f(i-1, j)

ii) replace，即把此字符替換為word2[j]，則問題轉化為f(i-1, j-1)

iii) Insert，即在此處增加一個字符word2[j]， 則問題轉化為f(i, j-1)

根據上述狀態轉移方程，很容易寫出代碼

    public int minDistance(String word1, String word2) {
       if (word1.equals(word2)) {
            return 0;
        }
        if (word1.length() == 0 || word2.length() == 0) {
            return Math.abs(word1.length() - word2.length());
        }
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= word2.length(); i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }