[high frequency interview questions] difficulty 1.5/5, LCS template questions

Title Description

This is a LeetCode Upper 「1143. Longest common subsequence 」 , The difficulty is 「 secondary 」.

Tag : 「 Longest common subsequence 」、「LCS」、「 Sequence DP」

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 .

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 ：

• text1 and   text2 It only consists of lowercase English characters .

Dynamic programming （ Whitespace technique ）

This is a way 「 Longest common subsequence （LCS）」 The naked question of .

For this kind of questions, use the following 「 State definition 」 that will do ：

On behalf of Before Characters 、 consider Before The characters of , The length of the longest common subsequence formed .

When there's a 「 State definition 」 after , Basically 「 Transfer equation 」 It's just about to come out ：

• s1[i]==s2[j] : . representative 「 Must use And when 」 LCS The length of .
• s1[i]!=s2[j] : . representative 「 Must not use （ But it is possible to use ） when 」 and 「 Must not use （ But it is possible to use ） when 」 LCS The length of .

Some coding details ：

I usually add a space to the beginning of a string , To reduce boundary judgment （ Subscript from 1 Start , And it's easy to construct scrollable 「 Valid values 」）.

Java Code ：

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        s1 = " " + s1; s2 = " " + s2;
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[n + 1][m + 1]; 

        //  Because there are additional spaces , We have the obvious initialization value （ The following two initialization methods are available ）
        // for (int i = 0; i <= n; i++) Arrays.fill(f[i], 1);
        for (int i = 0; i <= n; i++) f[i][0] = 1;
        for (int j = 0; j <= m; j++) f[0][j] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i] == cs2[j]) {
                    f[i][j] = f[i -1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        //  Subtract the space added at the beginning 
        return f[n][m] - 1;
    }
}

C++ Code ：

class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        s1 = " " + s1, s2 = " " + s2;
        int f[n+1][m+1];
        memset(f, 0, sizeof(f));

        for(int i = 0; i <= n; i++) f[i][0] = 1;
        for(int j = 0; j <= m; j++) f[0][j] = 1;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(s1[i] == s2[j]) {
                    f[i][j] = max(f[i-1][j-1] + 1, max(f[i-1][j], f[i][j-1]));
                } else {
                    f[i][j] = max(f[i-1][j], f[i][j-1]);
                }
            }
        }
        return f[n][m] - 1;
    }
};

• Time complexity ：
• Spatial complexity ：

Dynamic programming （ Using offset ）

Above 「 Append space 」 I'm used to it

in fact , We can also modify 「 State definition 」 To achieve recursion ：

On behalf of Before Characters 、 consider Before The characters of , The length of the longest common subsequence formed .

So the final It's our answer , As invalid value , Just leave it alone .

• s1[i-1]==s2[j-1] : . On behalf of the use of And The length of the longest common subsequence .
• s1[i-1]!=s2[j-1] : . Does not use The length of the longest common subsequence 、 Don't use The length of the longest common subsequence . The maximum of these two cases .

Java Code ：

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int[][] f = new int[n + 1][m + 1]; 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[n][m];
    }
}

Python3 Code ：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])
        return dp[m][n]

C++ Code ：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m + 1,vector<int>(n + 1,0));
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(text1[i - 1] == text2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

Golang Code ：

func longestCommonSubsequence(text1 string, text2 string) int {
    m := len(text1)
    n := len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if text1[i] == text2[j] {
                dp[i+1][j+1] = dp[i][j] + 1
            } else {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            }
        }
    }
    return dp[m][n]
}
func max(i int, j int) int {
    if i > j {
        return i
    }
    return j
}

• Time complexity ：
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series No.1143 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases