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

Longest common subsequence

Power button link

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” is a subsequence of “ABCDE”, but “AEC” is not a subsequence of “ABCDE”. 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.

Dynamic programming cleverly handles boundaries

Train of thought

Here we’re going to use a two-dimensional array to hold the longest common subsequence of two strings at different lengths

Dp [I][j] represents the result of the longest common self-sequence between text1.substr(0, I) and text2.substr(0,j).

We declare the length bit m of text1, the length bit n of text2, so we’re going to iterate through the string so that I is equal to the sum from 1 to m, j is equal to the sum from 1 to n

Each bit of text1 is text1[i-1] (the last bit of the string is text1[i-1]), and text2 is text2[J-1]

  • Text1. substr(0, I) and text1.substr(0,j) are empty strings “” and cannot be counted as subsequences, so the result is dp[0][j] and dp[I][0]

  • State transition: Declare dp array to hold the longest common subsequence of dp[I][j] (the longest common subsequence of the first i-bit string of Text1 and the first j-bit string of Text2)

In dynamic programming, the larger values of I and j depend on the smaller values of I and j. So when we compare two strings there are two results from the last digit, equal or unequal

If the ends are equal: Dp [I][j] = dp[I][j] = dp[I][J] = dp[I][J] = dp[I][J] = dp[I][J] +1

If the endpoints are not equal: if at least one of the two endpoints is not in the longest increasing subsequence, then removing the end of a string has no effect on the longest common subsequence.

// For example: Substr (0,j) str1 = 'abcd' str2 = 'efghc' Str3 = 'ABC' str4 = 'efghc' //1 str3 = 'ABCD' str4 = 'efgh' //0 // It is obvious that removing the last character of str1 has no effect on the longest common subsequence of str1 and str2Copy the code

Text1. substr(0,i-1) and text2.substr(0,j), then text1 plus a string to reach dp[I][j]; Or text1.substr(0, I) and text2.substr(0,j-1), and then text2 plus a string reaches dp[I][j]; So dp[I][j] is equal to the larger of the two, and the recursive formula is obtained

  • Recursive formula:
    • text1[i] === text2[j] dp[i][j] = dp[i-1][j-1]+1
    • text1[i] ! == text2[j] dp[i][j] = Math.max(dp[i-1][j],p[i][j-1])
var longestCommonSubsequence = function (text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() = > new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const c1 = text1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = text2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); }}}return dp[m][n];
}
Copy the code

To optimize the

We’re using the idea of scrolling arrays, and obviously, our dp two-dimensional array, we can think of it as a rectangular grid, with I and j representing the y-coordinate and y-coordinate, respectively.

Every time we calculate the next position, we’re going to rely on the top, the left, or the top left at most. So all we need is two rows of data, essentially two sum arrays

The one up here is called pre and the one that’s currently being calculated is called curr

So let’s just kill dp in our code, replace dp[I] with our curr, replace dp[i-1] with our prev, and then at the end of the first loop, next time prev=curr, curr equals the empty array and that reduces space complexity

The final curr or empty prev holds the final result, and returns the last bit of the prev

var longestCommonSubsequence = function (text1, text2) {
    const m = text1.length, n = text2.length;
    var pre = new Array(n + 1).fill(0)
    var curr = new Array(n + 1).fill(0)
    for (let i = 1; i <= m; i++) {
        const c1 = text1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = text2[j - 1];
            if (c1 === c2) {
                curr[j] = pre[j - 1] + 1;
            } else {
                curr[j] = Math.max(pre[j], curr[j - 1]);
            }
        }
        pre = curr
        curr = new Array(n + 1).fill(0)}return pre[pre.length-1];
}
Copy the code