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

When solving this problem, we must first observe how word1 becomes word2. Taking Example1 as an example, the lower left figure lists the distance from “horse” to “ros”. In the table, the vertical axis represents “horse”, and the horizontal axis represents “ros”.

In the first line, we first consider how to convert an empty string into “ros”.

• First, the empty string is converted to an empty string with a distance of 0.
• Second, the empty string is converted to “r”, and the distance is 1, because an “r” is to be inserted.
• Third, the empty string is converted to “ro” with a distance of 2 because an “r” and an “o” are to be inserted.
• Fourth, the empty string is transformed into “ros”, and the distance is 3.

In the second line, we consider how “h” can be converted to “ros” when there is only the first letter of “horse”. In the third line, we consider how “ho” can be converted to “ros”.

After observing the following left figure, we can discover some rules. The distance from the bottom “horse” to “r” in the lower right image is 4. We found the following formula:

In addition, we also found another rule, which is the blue part in the following right figure. When the last letters are the same, such as “ho” converting to “ro” and “hor” converting to “r”, then:

Combining the above two formulas, we can derive the following formula.

Therefore, this problem is changed to use the above formula to create the table in the figure below. The final answer will be the last element in the table, which is the green part.

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.