The topic of dry

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

Solution: dynamic programming

For me, the most important thing is to establish the recursion formula. First of all, to observe this problem, we need a two-dimensional array dp[][]

Tabulated to derive the dynamic transfer formula.

Here, when the positions of the elements are not equal, we take the maximum values above and to the left as the current longest common subsequence, and if they are the same, we take the common subsequence +1 of the position above the current I position.

Finally, we can get the state escape formula:

   if (text1[i - 1] == text2[j - 1]) {
       dp[i][j] = dp[i - 1][j - 1] + 1
   } else {
       dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
   }
Copy the code

Code implementation:

var longestCommonSubsequence = function (text1, text2) {
    let len1 = text1.length, len2 = text2.length;
    // Initialize the dp array
    let dp = new Array(len1 + 1).fill(0).map(() = > new Array(len2 + 1).fill(0))
    for (let i = 1; i < len1 + 1; i++) {
        for (let j = 1; j < len2 + 1; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
            }
        }
    }
    console.log(dp)
    return dp[len1][len2]
};
Copy the code