LeetCode 1143. Longest common subsequence

1143. Longest common subsequence

difficulty secondary

Given two strings text1 and text2, Returns the longest of these two strings Common subsequence The length of . If it doesn't exist Common subsequence , return 0 .

A string of Subsequence This is a new string ： It is to delete some characters from the original string without changing the relative order of the characters （ You can also delete no characters ） After the composition of the new string .

• for example ,"ace" yes "abcde" The subsequence , but "aec" No "abcde" The subsequence .

Two strings of Common subsequence Is the subsequence shared by these two strings .

Example 1：

 Input ：text1 = "abcde", text2 = "ace" 
 Output ：3  
 explain ： The longest common subsequence is  "ace" , Its length is  3 .

Example 2：

 Input ：text1 = "abc", text2 = "abc"
 Output ：3
 explain ： The longest common subsequence is  "abc" , Its length is  3 .

Example 3：

 Input ：text1 = "abc", text2 = "def"
 Output ：0
 explain ： The two strings have no common subsequence , return  0 .

Tips ：

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 It only consists of lowercase English characters .

Answer key

​ This question is also a typical one dp subject , If you have done the longest ascending subsequence, etc , It is helpful to understand and solve this problem . Let's talk about the longest common subsequence （LCS：Longest Common Subsequence） Well .

​ Subsequence and substring are different , Substrings must be continuous , Subsequences only need to be in the same order , But there is no guarantee of continuity .

​ The longest common subsequence is , In two strings , Can we find the longest continuous or discontinuous subsequence , If we don't understand dynamic planning practices , In fact, it can also be brutally cracked , Is to find all subsequences of two strings , If t1 The length is n,t2 The length is m, that t1 There are subsequences of 2^{n individual ,t2 There are subsequences of 2}m individual , The time complexity is as high as 2^(n+m).

​ That certainly can't consider brute force cracking , How does dynamic programming solve the problem .

​ We have to use a two-dimensional auxiliary array to record the length of the longest common subsequence ,dp[i] [j] The length of the record is i And length j The longest common subsequence length of the string of . With auxiliary arrays , Then we need to find the dynamic programming transition equation according to the state .

• If a string length is 0 The empty string of , The length of another string cannot have a common subsequence , namely dp[i] [0] = dp[0] [j] = 0

• If t1[i] = t2[j], that dp[i] [j] = dp[i - 1] [j - 1] + 1, because dp[i - 1] [j - 1] The record is t1[0: i - 1] and t2[0: j - 1] The longest common subsequence length of , If t1[i] = t2[j] Words , Add one to the length .

  ​ for example acef and def, When variable to ace and de yes , The longest common subsequence length is 1, Only the last e identical , Then join f after , The longest common subsequence length is 2, namely 1(dp[i - 1] [j -1]) + 1

• If t1[i] ≠ t2[j],dp[i] [j] What should it be . We should think about dp[i] [j] What does it mean ,dp[i] [j] Said is t1[0: i] and t2[0: j] The longest common subsequence length of , Then we should take dp[i] [j - 1] and dp[i - 1] [j] The largest of them .

  ​ Why is the biggest one of the two , because dp[i] [j - 1] representative t1[i] and t2[j-1],dp[i - 1] [j] representative t1[i-1] and t2[j], These two states include t1[i] ≠ t2[j] The longest possible common subsequence of the .

class Solution {
    
    public int longestCommonSubsequence(String text1, String text2) {
    
        int len1 = text1.length();// length 1
        int len2 = text2.length();// length 2
        int[][] dp = new int[len1 + 1][len2 + 1];// The dynamic array 
        for(int i = 1; i <= len1; i++){
    
            for(int j = 1; j <= len2; j++){
    
                if(text1.charAt(i - 1) == text2.charAt(j - 1)){
    //t1[i] = t2[j], that dp[i] [j] = dp[i - 1] [j - 1] + 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
    //t1[i] ≠ t2[j], Then take dp[i] [j - 1] and dp[i - 1] [j] The largest of them 
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }
}