mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-04 07:29:47 +08:00
86d333ee94
* chore: Switch to Node 20 + Vitest * chore: migrate to vitest mock functions * chore: code style (switch to prettier) * test: re-enable long-running test Seems the switch to Node 20 and Vitest has vastly improved the code's and / or the test's runtime! see #1193 * chore: code style * chore: fix failing tests * Updated Documentation in README.md * Update contribution guidelines to state usage of Prettier * fix: set prettier printWidth back to 80 * chore: apply updated code style automatically * fix: set prettier line endings to lf again * chore: apply updated code style automatically --------- Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
60 lines
1.9 KiB
JavaScript
60 lines
1.9 KiB
JavaScript
/*
|
||
Problem:
|
||
Given two sequences, find the length of longest subsequence present in both of them.
|
||
A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.
|
||
For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”
|
||
|
||
Our Solution:
|
||
We use recursion with tabular memoization.
|
||
Time complexity: O(M x N)
|
||
Solving each subproblem has a cost of O(1). Again, there are MxN subproblems,
|
||
and so we get a total time complexity of O(MxN).
|
||
Space complexity: O(M x N)
|
||
We need to store the answer for each of the MxN subproblems.
|
||
|
||
Improvement:
|
||
It's possible to optimize space complexity to O(min(M, N)) or time to O((N + r)log(N))
|
||
where r is the number of matches between the two sequences. Try to figure out how.
|
||
|
||
References:
|
||
[wikipedia](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem)
|
||
[leetcode](https://leetcode.com/problems/longest-common-subsequence/)
|
||
*/
|
||
|
||
/**
|
||
* Finds length of the longest common subsequence among the two input string
|
||
* @param {string} str1 Input string #1
|
||
* @param {string} str2 Input string #2
|
||
* @returns {number} Length of the longest common subsequence
|
||
*/
|
||
function longestCommonSubsequence(str1, str2) {
|
||
const memo = new Array(str1.length + 1)
|
||
.fill(null)
|
||
.map(() => new Array(str2.length + 1).fill(null))
|
||
|
||
function recursive(end1, end2) {
|
||
if (end1 === -1 || end2 === -1) {
|
||
return 0
|
||
}
|
||
|
||
if (memo[end1][end2] !== null) {
|
||
return memo[end1][end2]
|
||
}
|
||
|
||
if (str1[end1] === str2[end2]) {
|
||
memo[end1][end2] = 1 + recursive(end1 - 1, end2 - 1)
|
||
return memo[end1][end2]
|
||
} else {
|
||
memo[end1][end2] = Math.max(
|
||
recursive(end1 - 1, end2),
|
||
recursive(end1, end2 - 1)
|
||
)
|
||
return memo[end1][end2]
|
||
}
|
||
}
|
||
|
||
return recursive(str1.length - 1, str2.length - 1)
|
||
}
|
||
|
||
export { longestCommonSubsequence }
|