“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

1, the title

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings. If no common subsequence exists, return 0.

A subsequence of a string is a new string made up of the original string without changing the relative order of the characters by deleting some characters (or none).

  • For example,"ace" 是 "abcde"Of, but"aec"not"abcde"Subsequence of.

A common subsequence of two strings is a subsequence that is shared by both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace", which has length 3.Copy the code

Example 2:

Input: text1 = "ABC ", text2 =" ABC "Output: 3 Explanation: The longest common subsequence is" ABC ", which has length 3.Copy the code

Example 3:

Input: text1 = "ABC ", text2 = "def" Output: 0 Explanation: The two strings have no common subsequence, return 0.Copy the code

Tip:

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2Contains only lowercase English characters.

2, train of thought

(Dynamic programming)O(nm)O(nm) O(nm)

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings (the subsequence can be discontinuous).

Sample:

As shown in the example, the longest common subsequence of the string abcde and the string ace is ace, of length 3. The longest common subsequence problem is a typical two-dimensional dynamic programming problem.

State representation: define f[I][j] to represent the longest common subsequence length of the [1, I] interval of the string text1 and the [1,j] interval of the string Text2 (the subscript starts at 1).

State calculation:

Text1 [I] and Text2 [j] can be divided into two kinds of decisions:

  • 1, iftext1[i] == text2[j]That is, the last bit of the two strings is equal, then the problem becomes a stringtext1the[1,j-1]Intervals and stringstext2the[1,j-1]The longest common subsequence length of the interval plus one, i.ef[i][j] = f[i - 1][j - 1] + 1. (subscript from1Start)

  • 2, iftext1[i] ! = text2[j]That is, the last bit of two strings is not equal, then the stringtext1the[1,i]Intervals and stringstext2the[1,j]The longest common subsequence length of the interval cannot be extended, sof[i][j]Will inheritf[i-1][j]withf[i][j-1]The greater value of, i.ef[i][j] = max(f[i - 1][j],f[i][j - 1]). (subscript from1Start)

  • As the picture above shows: We comparetext1[3]withtext2[3]And found that'f'Is not equal to'e'So that thef[3][3]Cannot be extended on the original basis, therefore inherit"ac"with"cfe" ."acf"with"cf"The greater value in the longest common subsequence of, i.ef[3][3] = max(f[2][3] ,f[3][2]) = 2.

Therefore, the state transition equation is:

F [I][j] = f[i-1][J-1] + 1, when text1[I] == text2[j]

F [I] [j] = Max (f [j], [I – 1] f [I] [1]), when text1 [I]! = text2 [j].

Initialization:

F [I][0] = f[0][j] = 0, (0 <= I <=n, 0<=j<=m)

The longest common subsequence length of an empty string and a long string must be 0.

Implementation details:

The state we defined means that both f array and text array index start at 1, while the text array index given by the question starts at 0. In order to correspond to one, when judging whether the last digit of text1 and Text2 array is equal, the first digit is wrong. Text1 [i-1] and Text2 [J-1] are used to judge.

Time complexity analysis: O(nm)O(nm)O(nm), where NNN and MMM are the lengths of text1 and Text2 respectively.

C++ code

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> f(n + 1.vector<int>(m + 1.0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]); }}}returnf[n][m]; }};Copy the code

4. Java code

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(), m =  text2.length();
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (text1.charAt(i - 1) == text2.charAt(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]); }}}returnf[n][m]; }}Copy the code

Original link: 1143. Longest common subsequence