LeetCode 583. Deleting two strings

583. Deletion of two strings

difficulty secondary

Give two words word1 and word2 , Return makes word1 and word2 identical The required The minimum number of steps .

Every step You can delete a character from any string .

Example 1：

 Input : word1 = "sea", word2 = "eat"
 Output : 2
 explain :  The first step will be  "sea"  Turn into  "ea" , The second step will be  "eat " Turn into  "ea"

Example 2:

 Input ：word1 = "leetcode", word2 = "etco"
 Output ：4

Tips ：

• 1 <= word1.length, word2.length <= 500
• word1 and word2 Only lowercase letters

Answer key

​ This problem lets us find the minimum number of steps for bidirectional conversion of two strings , Because I have done the title of the longest common subsequence , So it's easy to figure out how to solve , Is to find the common subsequence of two characters , Then the other characters of the common subsequence are deleted from both strings , That's the final result .

• First find the length of the longest common subsequence
• Then subtract the length of the longest common subsequence from the length of the two strings

class Solution {
    
    public int minDistance(String word1, String word2) {
    
        int l1 = word1.length();//word1 length 
        int l2 = word2.length();//word2 length 
        int[][] dp = new int[l1 + 1][l2 + 1];// The dynamic array 
        for(int i = 1; i <= l1; i++){
    
            for(int j = 1; j <= l2; j++){
    
                if(word1.charAt(i -1) == word2.charAt(j - 1)){
    // Same letter , The length of the longest common subsequence plus one （ In state i-1,j-1 Add one to the case of ）
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
    // The letters are different , Take the State i-1,j Or state i,j-1 Smallest of 
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return l1 + l2 - 2 * dp[l1][l2];// Subtract the length of the longest common subsequence from the length of the two strings 
    }
}