Subsequence --- edit distance

392. Judging subsequences

subject

Given string s and t , Judge s Is it t The subsequence .
A subsequence of the string is the original string delete some （ It can also be done without deleting ） A new string of characters formed without changing the relative positions of the remaining characters .（ for example ,"ace" yes "abcde" A subsequence of , and "aec" No ）.
Example ：

Ideas

1. determine dp Array （dp table） And the meaning of subscripts
dp[i][j] Denotes the following i-1 String ending with s, And the following j-1 String ending with t, The length of the same subsequence is dp[i][j].
2. Determine the recurrence formula
if (s[i - 1] == t[j - 1]) -----> t Found a character in s It also appears in —> dp[i][j] = dp[i - 1][j - 1] + 1;
if (s[i - 1] != t[j - 1]) -----> amount to t To delete an element , Continue matching -------> dp[i][j] = dp[i][j - 1]
3. initialization
Out dp[i][j] All depend on dp[i - 1][j - 1] and dp[i][j - 1], therefore dp[0][0] and dp[i][0] It must be initialized .
dp[0][0] = 0;
dp[i][0] Denotes the following i-1 String ending with , The same subsequence length as the empty string , So for 0.
4. Determine the traversal order
The traversal order should also be from top to bottom , From left to right

Code

class Solution {
    
    public boolean isSubsequence(String s, String t) {
    
        //dp[i][j]  Denotes the following i-1 String ending with s, And the following j-1 String ending with t, The length of the same subsequence is dp[i][j].
        int len1 = s.length();
        int len2 = t.length();
        int[][] dp = new int[len1+1][len2+1];
        // initialization  dp[0][0]  and  dp[i][0]  All zero , Don't take it out and initialize it separately 
        for(int i = 1; i <= len1; i++){
    
            for(int j =1; j <= len2; j++){
    
                if(s.charAt(i-1) == t.charAt(j-1)){
    
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
    
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[len1][len2] == len1;
    }
}

115. Different subsequences

subject

Given a string s And a string t , Calculated at s In the subsequence of t Number of occurrences .
One of the strings Subsequence Refer to , By deleting some （ It can also be done without deleting ） Character and does not interfere with the relative position of the remaining characters of the new string .（ for example ,“ACE” yes “ABCDE” A subsequence of , and “AEC” No ）
Example ：

Ideas

1. determine dp Array （dp table） And the meaning of subscripts
dp[i][j]： With i-1 For the end of s Subsequence in Appear to j-1 For the end of t The number of dp[i][j].
2. Determine the recurrence formula
Is to analyze Two cases :
s[i - 1] And t[j - 1] equal
s[i - 1] And t[j - 1] It's not equal
When s[i - 1] And t[j - 1] When equal ,dp[i][j] It can consist of two parts .
Part of it is with s[i - 1] To match , Then the number is dp[i - 1][j - 1].
Part of it is not s[i - 1] To match , The number is dp[i - 1][j]
(1) When s[i - 1] And t[j - 1] When equal ,dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
(2) When s[i - 1] And t[j - 1] When they are not equal ,dp[i][j] Only one part , no need s[i - 1] To match , namely ：dp[i - 1][j] dp[i][j] = dp[i - 1][j];
3. initialization
dp[i][0] and dp[0][j] It must be initialized .
dp[i][0] Express ： With i-1 For the end of s You can delete any element , The number of empty strings . The number of empty strings is 1.
dp[0][j]： An empty string s You can delete any element , Appear to j-1 String ending with t The number of .dp[0][j] Some are 0
4. Determine the traversal order
It must be from top to bottom , From left to right

Code

class Solution {
    
    public int numDistinct(String s, String t) {
    
        //dp[i][j]： With i-1 For the end of s Subsequence   in   Appear to j-1 For the end of t The number of dp[i][j].
        int len1 = s.length();
        int len2 = t.length();
        int[][] dp = new int[len1+1][len2+1];
        // initialization ：dp[0][j] Always be 0
        for(int i = 0; i <= len1; i++){
    
            dp[i][0] = 1;
        }
        for(int i = 1; i <= len1; i++){
    
            for(int j = 1; j <= len2; j++){
    
                if(s.charAt(i-1) == t.charAt(j-1)){
    
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                }else{
    
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[len1][len2];
    }
}

583 Deletion of two strings

subject

Give two words word1 and word2 , Return makes word1 and word2 The same minimum number of steps required .
Every step You can delete a character from any string .
Example ：

Ideas

1. determine dp Array （dp table） And the meaning of subscripts
dp[i][j]： With i-1 String ending with word1, And with j-1 Bit terminated string word2, To achieve equality , The minimum number of times an element needs to be deleted .
2 Determine the recurrence formula
（1） When word1[i - 1] And word2[j - 1] At the same time ,dp[i][j] = dp[i - 1][j - 1];
（2） When word1[i - 1] And word2[j - 1] Different times , There are three situations ：
Situation 1 ： Delete word1[i - 1], The minimum number of operations is dp[i - 1][j] + 1
Situation two ： Delete word2[j - 1], The minimum number of operations is dp[i][j - 1] + 1
Situation three ： Delete at the same time word1[i - 1] and word2[j - 1], The minimum number of operations is dp[i - 1][j - 1] + 2
Finally, of course, take the minimum , So when word1[i - 1] And word2[j - 1] Different times , The recursive formula ：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
3. initialization
dp[i][0] and dp[0][j] It must be initialized .
dp[i][0]：word2 Is an empty string , With i-1 String ending with word1 How many elements to delete , Talent and word2 The same , Obviously dp[i][0] = i.
dp[0][j] The same is true of

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
The recursive formula dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1); and dp[i][j] = dp[i - 1][j - 1] It can be seen that dp[i][j] It's all based on the top left 、 Just above 、 Pushed right to the left .
So the traversal must be from top to bottom , From left to right , This guarantee dp[i][j] It can be calculated according to the value calculated before .

Code

class Solution {
    
    public int minDistance(String word1, String word2) {
    
        //dp[i][j]： With i-1 String ending with word1, And with j-1 Bit terminated string word2, To achieve equality , The minimum number of times an element needs to be deleted .
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1+1][len2+1];
        // initialization 
        for(int i = 0; i <= len1; i++){
    
            dp[i][0] = i;
        }
        for(int j = 0; j <= len2; j++){
    
            dp[0][j] = j;
        }
        for(int i = 1; i <= len1; i++){
    
            for(int j = 1; j <= len2; 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]+2,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                }
            }
        }
        return dp[len1][len2];

    }
}

72. Edit distance

subject

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. determine dp Array （dp table） And the meaning of subscripts
dp[i][j] Denotes the following i-1 String ending with word1, And the following j-1 String ending with word2, The nearest edit distance is dp[i][j].
2. Determine the recurrence formula

if (word1[i - 1] == word2[j - 1])
     Do not operate   ----->  dp[i][j] = dp[i - 1][j - 1];
if (word1[i - 1] != word2[j - 1])
     increase 
     Delete 
     in 

if (word1[i - 1] != word2[j - 1])
Operation 1 ： Remove elements
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 edit distance of Plus an operation
dp[i][j] = dp[i - 1][j] + 1
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
dp[i][j] = dp[i][j - 1] + 1;

Operation two ： Additive elements
**!!! word2 Add an element , amount to word1 Delete an element ,** for example word1 = “ad” ,word2 = “a”,word1 Remove elements ’d’ and word2 Add an element ’d’, become word1=“a”, word2=“ad”, The final operand is the same ！

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 . Empathy ,word2 Replace word2[j - 1], Make it relate to word1[i - 1] identical , It is also the following formula
namely dp[i][j] = dp[i - 1][j - 1] + 1;

！！！ Sum up , When if (word1[i - 1] != word2[j - 1]) Take the smallest , namely ：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

3. initialization
dp[i][0] and dp[0][j]
dp[i][0] ： By subscript i-1 String ending with word1, And empty string word2, The nearest edit distance is dp[i][0].
that dp[i][0] It should be i, Yes word1 Delete all the elements in the , namely ：dp[i][0] = i; Empathy dp[0][j] = j;
4. Determine the traversal order

Code

class Solution {
    
    public int minDistance(String word1, String word2) {
    
        //dp[i][j]  Denotes the following i-1 String ending with word1, And the following j-1 String ending with word2, The nearest edit distance is dp[i][j].
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1+1][len2+1];
        // initialization 
        for(int i = 0; i <= len1; i++){
    
            dp[i][0] = i;      
        }
        for(int j = 0; j <= len2; j++){
    
            dp[0][j] = j;       
        }
        for(int i = 1; i <= len1; i++){
    
            for(int j = 1; j <= len2; 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]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);            
                }
            }
        }
        return dp[len1][len2];

    }
}