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]
};
Top comments (0)