72. Edit Distance

Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

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

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

Solution

在解此題時，我們要先觀察 word1 如何變成 word2。以 Example1 為例，左下圖列出 “horse” 轉變成 “ros” 的 distance。表中，縱軸表示 “horse”，而橫軸表示 “ros”。

第一行，我們先考慮如何空字串轉變成 “ros”。

• 第一，空字串轉變成空字串，distance 為 0。
• 第二，空字串轉變成 “r”，distance 為 1，因為要插入一個 “r”。
• 第三，空字串轉變成 “ro”，distance 為 2，因為要插入一個 “r” 和一個 “o”。
• 第四，空字串轉變成 “ros”，distance 為 3。

第二行，我們考慮當只有 “horse” 的第一個字母時，也就是 “h” 要如何轉變成 “ros”。第三行，我們考慮 “ho” 要如何轉變成 “ros”。

觀察左下圖後，我們可以發現一些規則。在右下圖的最下面的 “horse” 轉變成 “r” 的距離是 4。我們發現以下的公式：

另外，我們還發現另一個規則，也就是右下圖中藍色的部分。當最後的字母相同時，如 “ho” 轉變成 “ro” 和 “hor” 轉變成 “r”，則：

結合上述兩個公式，我們可以得出以下公式。

因此，此題便轉變為，利用上面的公式來建立下圖中的表格。最後的答案就會在表格中的最後一個元素，也就是途中綠色的部分。

Dynamic Programming

• Time:
• Space:

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

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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][j - 1] + 1, dp[i - 1][j - 1] + 1));
                }
            }
        }

        return dp[m][n];
    }
}

參考

• 72. Edit Distance, LeetCode.
• 72. Edit Distance, LeetCode Solutions.