1143. Longest Common Subsequence (javascript solution)

Description:

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

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

Solution:

Time Complexity : O(n^2)
Space Complexity: O(n^2)

var longestCommonSubsequence = function(text1, text2) {
    // Create dp table
    const dp = Array(text1.length+1).fill(0).map(() => Array(text2.length+1).fill(0))
    for(let i = 1; i < dp.length; i++) {
        for(let j = 1; j < dp[i].length; j++) {
            // If the letters match, look diagonally to get the max subsequence before this letter and add one
            if(text1[i-1]===text2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                // If there is no match, set the cell to the previous current longest subsequence
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
            }
        }
    }
    return dp[text1.length][text2.length]
};

Blog

1143. Longest Common Subsequence (javascript solution)

codingpineapple

Description:

Solution:

Join Our Newsletter. No Spam, Only the good stuff.

Related