“This is the 23rd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

The title

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings.

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.

Returns 0 if the two strings have no common subsequence.

Example 1:

Input: text1 = “abcde”, text2 = “ace” Output: 3 Explanation: The longest common subsequence is “ace”, which has length 3.

Example 2: Input: text1 = “ABC “, text2 =” ABC “Output: 3 Explanation: The longest common subsequence is” ABC “, which has length 3.

Example 3: Input: text1 = “ABC “, text2 = “def” Output: 0 Explanation: The two strings have no common subsequence, return 0.

Tip:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000 The entered string contains only lowercase English characters

Their thinking

LeetCode1143. The longest common subsequence is obviously LeetCode718. LeetCode718. The longest repeating subarray is roughly the same, and dynamic programming is used to solve the problem, but the meaning of DP array and recursive formula under various conditions are different.

Dynamic programming

  1. The definition of dp [I] [j]

Dp [I][j] indicates how many pairs of the same letters precede text1 string index I and text1 string index j

  1. State transition equation

There are two main cases: Text1 [i-1] is the same as Text2 [J-1]; text1[i-1] is the same as Text2 [J-1]; text1[i-1] is different from Text2 [J-1]. So dp[I][j] = DP [i-1][j-1] + 1; If text1[i-1] is not the same as Text2 [J-1], look at the longest common subsequence of text1[0, i-2] and Text2 [0, J-1]. Take the largest. Dp [I][j] = Max (DP [I][J], DP [I][J-1]);

  1. How is a DP array initialized

Dp [I][0] = 0; dp[I][0] = 0; Similarly, dp[0][j] is also 0. All the other subscripts are covered by the recursion formula, and you can start with whatever you want, so you’re going to start with 0.

  1. Determine the traversal order

From the recursion formula, we can see that there are three directions that can derive dp[I][j], left, top left, and top, so in order to recurse, these three directions are all computed values, so we have to traverse the matrix from front to back, top to bottom

var longestCommonSubsequence = function(text1, text2) {
     let la = text1.length;
     let lb = text2.length;
     let dp = Array.from(Array(la + 1), () = > Array(lb + 1).fill(0));
     for (let i = 1; i <= la; i++) {
        for (let j = 1; j <= lb; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                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[la][lb];
 }

Copy the code