LeetCode 72. Edit distance

72. Edit distance

difficulty difficult

Here are two words for you word1 and word2, Please return to word1 convert to word2 The minimum number of operands used .

You can do the following three operations on a word ：

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

Example 1：

 Input ：word1 = "horse", word2 = "ros"
 Output ：3
 explain ：
horse -> rorse ( take  'h'  Replace with  'r')
rorse -> rose ( Delete  'r')
rose -> ros ( Delete  'e')

Example 2：

 Input ：word1 = "intention", word2 = "execution"
 Output ：5
 explain ：
intention -> inention ( Delete  't')
inention -> enention ( take  'i'  Replace with  'e')
enention -> exention ( take  'n'  Replace with  'x')
exention -> exection ( take  'n'  Replace with  'c')
exection -> execution ( Insert  'u')

Tips ：

• 0 <= word1.length, word2.length <= 500
• word1 and word2 It's made up of lowercase letters

Answer key

​ The solution to this problem is really difficult to write , It is difficult for me to describe , But the process of typing tables is easy to understand , Here you need a two-dimensional array dp Record the shortest editing distance .

• initialization

  ​ When a string is empty , To change to another string , The shortest editing distance is the length of another string , So when initializing, the 0 That's ok , The first 0 Columns are equal to the current subscript .

• Dynamic transfer equation

  ​ When both strings are not empty , To convert to the same string , You can insert , You can delete , Can replace , Then what is the shortest , This is also the result of our request .

  ​ Traverse to the string s1 The first i A subscript ,s2 The first j When there are two subscripts ,s1[i] May and s2[j] equal , Maybe not s2[j] equal .

  • When s1[i] = s2[j] when , You don't need any operation , Directly equal to the state dp[i-1] [j-1]
  • When s1[i] ≠ s2[j] when , You can insert , You can delete , Can replace , In order to find the shortest , We need to find dp[i - 1] [j],dp[i] [j - 1],dp[i - 1] [j - 1] The smallest of all
    • dp[i - 1] [j] Express s1 The length is i-1 and s2 The length is j The shortest editing distance , because s1[i] ≠ s2[j], At least editing is in s1 Of the i Change the position to s2[j], Only one operation is needed
    • dp[i] [j-1] ditto
    • dp[i - 1] [j - 1] ditto , Just replace the letters of any string with the letters of another string .

class Solution {
    
    public int minDistance(String word1, String word2) {
    
        int n = word1.length();//word1 The length of 
        int m = word2.length();//word2 The length of 

        if(n * m == 0){
    // One of the strings is... Long 0
            return n + m;
        }

        int[][] dp = new int[n + 1][m + 1];// Dynamic programming array 

        for(int i = 0; i <= n ; i++){
    // initialization 
            dp[i][0] = i;
        }

        for(int j = 0; j <= m; j++){
    // initialization 
            dp[0][j] = j;
        }

        for(int i = 1; i <= n; i++){
    // Print table traversal 
            for(int j = 1; j <= m; j++){
    
                int up = dp[i - 1][j] + 1;// In the i Add a letter to each position , operation +1
                int left = dp[i][j - 1] + 1;// In the j Add a letter to each position , operation +1
                int up_left = dp[i - 1][j - 1];//word1[i] = word2[j], No need to operate 
                if(word1.charAt(i - 1) != word2.charAt(j - 1)){
    //word1[i] ≠ word2[j], Need to operate 
                    up_left += 1;
                }
                dp[i][j] = Math.min(up_left, Math.min(up, left));// Get the smallest editing distance among so many operations 
            }
        }
        return dp[n][m];
    }
}