Leetcode-72. Edit Distance

Info

📖 72. Edit Distance

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.

Thinking

• Operation: Add + / Delete - / Replace r
• Cost: Replace == Add == Delete. Not prefer add & delete (prefer replace which just cost 1 step)
• Using matrix. Horizontal axis is word1, Vertical axis is word2 ❓
• DP might work, but how ❓

Solution

DP

Precontional Rules

Understand the below rule (Take “abcde” as A, “qwe” as B, we need to convert B to A)

• Adding a letter in A equals Deleting a letter in B (take example of “doge” and “dog”)
• Adding a letter in B equals Deleting a letter in A (Same inference)
• Replacing a letter in A equals Replacing a letter in B

So we actually get three actions (simplified action “Delete”)

• Add a letter in A
• Add a letter in B
• Replace a letter in B

So we get a DP bucket to handle this question

dp[i][j] indicates the edit distance for str A.substring(0, i) to convert to B.substring(0, j)

So it’s running dp for both objects(I tried to apply dp method, but just one object/direction, that’s why I failed)

Finally we get this inference based on DP:

$$dp[i][j]=\{\begin{array}{l}min(dp[i-1][j]-1,dp[i][j-1]-1,dp[i-1][j-1])(A[i]==B[i])\\ min(dp[i-1][j]-1,dp[i][j-1]-1,dp[i-1][j-1])(A[i]\ne B[i])\end{array}$$

Why the rule works?

Take A: abcde B: qwe

• If we know A -> B costs X steps, then abcdef -> qwe = abcdef -> abcde -> qwe (Minimum cost = X + 1)
• If we know A -> B costs X steps, then abcde -> qwef = abcdef -> qwe -> qwef (Minimum cost = X + 1)
• For dp[i - 1][j - 1]
  • If we know A -> B costs X steps, then abcdef -> qwef = (abcde)f -> (qwe)f (Minimum cost = X)
  • If we know A -> B costs X steps, then abcdef -> qweg = (abcde)f -> (abcde)g -> (qwe)g (Minimum cost = X + 1)

Notice: we only focus action in the end of the str, cause we are using dp thought.

So we can get the final dynamic programming rule:

$$dp[i][j]=\{\begin{array}{l}min(dp[i-1][j]-1,dp[i][j-1]-1,dp[i-1][j-1])(A[i]==B[i])\\ min(dp[i-1][j]-1,dp[i][j-1]-1,dp[i-1][j-1]+1)(A[i]\ne B[i])\end{array}$$

Convert HORSE to ROS

	#	R	O	S
#	0	1	2	3
H	1	1	2	3
O	2	2	1	3
R	3	2	2	2
S	4	3	3	2
E	5	4	4	3

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        // Init #
        for (int i = 0; i < word1.length() + 1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < word2.length() + 1; i++) {
            dp[0][i] = i;
        }
        // DP
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                int min = 0;
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1]));
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

Result-1

Reflection

• When handling problems related to Array, there is a high feasibility of using DP notion, so pay attention to that case.
• When we do try to use DP thought, be sure to find a feasible formula to summarize the prototype of the question, then we can move on. If not, it’s not dp.