12. < tag dynamic programming and subsequence, subarray> lt.72. edit distance

lt.72. Edit distance

[ Case needs ]

[ Thought analysis . Dynamic programming ]

1. determine dp The meaning of arrays and subscripts

dp[i][j] Express :
By subscript i - 1 String ending with word1( That is, the length is i String word1), And the following j - 1 String ending with word2, The nearest edit distance is dp[i][j];
Here's to emphasize ： Why should subscripts be expressed i-1 For the ending string , Why doesn't it mean subscript i For the ending string ？
use i It's OK to say ！ But I unify the following i-1 String ending with , It's easy to understand in the following recursive formula .

2. Determine the recurrence formula
   When determining the recurrence formula , First of all, we should consider several operations of editing :

if(word1[i - 1] == word2[i- 1])  Do not operate 
if(word[i- 1] != word2[i - 1]){
    
	 increase / Delete / Change 
}

that , if (word1[i - 1] != word2[j - 1]), It's time to edit , How to edit ？

1. Operation 1 : word1 Delete an element , So it's the following i - 2 For the end of word1 And j - 1 For the end of word2 The nearest editing distance plus one operation ., namely dp[i][j] = dp[ i - 1][j] + 1;
2. Operation two , word2 Delete an element , So it's the following i - 1 For the end of word1 And j-2 For the end of word2 The nearest edit distance of Plus an operation , namely dp[i][j] = dp[i][j - 1] + 1;
   
3. Operation three . Replacement elements , Operation three ： Replacement elements ,word1 Replace word1[i - 1], Make it relate to word2[j - 1] identical , There is no need to add elements at this time , So the following i-2 For the end of word1 And j-2 For the end of word2 The nearest edit distance of Add an operation to replace the element .
   namely dp[i][j] = dp[i - 1][j - 1] + 1;

• therefore , The recurrence formula is as follows :

if (word1[i - 1] == word2[j - 1]) {
    
    dp[i][j] = dp[i - 1][j - 1];
}
else {
    
    dp[i][j] = min({
    dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}

3. dp Initialization of an array

Let's review dp[i][j] The definition of ;
dp[i][j] The length is j, Namely subscript i- 1 a null-terminated string word1, And the following are marked j - 1 String ending with word2, The nearest edit distance is dp[i][j]
Again because , We know from the recursive formula , It needs to be initialized dp[0][0], dp[i][0], dp[0][j] Three elements .
So what do they represent ?
dp[i][0] ： By subscript i-1 String ending with word1, And empty string word2, The nearest edit distance is dp[i][0], Obviously i, Delete immediately i Time
that dp[i][0] It should be i, Yes word1 Delete all the elements in the , namely ：dp[i][0] = i;
Empathy , Empathy dp[0][j] = j;

for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

4. Determine the traversal order
   

5. Give an example to deduce dp Array
   

[ Code implementation ]

class Solution {
    
    public int minDistance(String word1, String word2) {
    
        int len1 = word1.length();
        int len2 = word2.length();

        //1. dp Array , dp[i][j] The length is i String word1 And length j String word2, word1 Convert to word2 Editing distance required 
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        //2.  Determine the recurrence formula ;
        //word1[i]  and word[j]  At some index ,  There are two cases of equal or unequal characters 
        // If the characters are equal ,  The editing distance of our index here is 0, 
        // If the characters are not equal ,  We have three operation modes 
        //1.  Delete a character ,  If you remove word1[i - 1] Be able to make word1[i - 2] == word2[j - 1], 
         that , dp[i][j] = dp[i - 1][j] + 1;
         If you remove word2[i - 1] Can make word1[i - 1] == word2[j - 2]
        / that , dp[i][j] = dp[i][j - 1] + 1;
        //2.  Insert a character ,  In fact, it has the same effect as deleting 
        //3.  Replace a character . Replace word1[i]  perhaps word[j]
         that . dp[i][j] = dp[i - 1][j - 1] + 1;

        //3.  initialization ,  According to the recurrence formula , dp[0][0], dp[i][0], dp[0][j] It needs to be initialized 
        // according to dp Definition of array ,  It's easy to think of initialization values , 
        for(int i = 1; i <= len1; i++){
    
            dp[i][0] = i;
        }

        for(int j = 1; j <= len2; j++){
    
            dp[0][j] = j;
        }


        //4.  Recurrence 
        for(int i = 1; i < len1 + 1; i++){
    
            for(int j = 1; j < len2 + 1; j++){
    
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
    
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
    
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }

        return dp[len1][len2];
    }
}