Problem
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.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Constraints:
1 <= text1.length, text2.length <= 1000
text1
andtext2
consist of only lowercase English characters.
Solution
/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
var longestCommonSubsequence = function(text1, text2) {
var dp = Array(text1.length).fill(0).map(() => Array(text2.length));
var dfs = function(i, j) {
if (i === text1.length || j === text2.length) return 0;
if (dp[i][j] !== undefined) return dp[i][j];
if (text1[i] === text2[j]) {
dp[i][j] = 1 + dfs(i + 1, j + 1);
} else {
dp[i][j] = Math.max(
dfs(i + 1, j),
dfs(i, j + 1),
dfs(i + 1, j + 1),
);
}
return dp[i][j];
};
dfs(0, 0, 0);
return dp[0][0];
};
Explain:
nope.
Complexity:
- Time complexity : O(n * m).
- Space complexity : O(n * m).