Skip to content

Commit bf24ea3

Browse files
trekhlebtrekhleb
committed
Add LCS.
1 parent 0e46d3e commit bf24ea3

4 files changed

Lines changed: 100 additions & 2 deletions

File tree

‎README.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -39,11 +39,11 @@
3939
* [Least Common Multiple](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/least-common-multiple) (LCM)
4040
* [Fisher–Yates Shuffle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fisher-yates) - random permutation of a finite sequence
4141
* **String**
42-
* [Levenshtein Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences (DP approach)
42+
* [Levenshtein Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences (dynamic programming approach)
4343
* [Hamming Distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/hamming-distance) - number of positions at which the symbols are different
4444
* [Knuth–Morris–Pratt Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/knuth-morris-pratt) - substring search
4545
* [Rabin Karp Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/rabin-karp) - substring search
46-
* Longest common subsequence
46+
* [Longest Common Subsequence](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/longest-common-subsequnce) (LCS)
4747
* longest common substring
4848
* **Search**
4949
* [Binary Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search)

‎src/algorithms/string/longest-common-subsequnce/README.md‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
# Longest common subsequence problem
2+
3+
The longest common subsequence (LCS) problem is the problem of finding
4+
the longest subsequence common to all sequences in a set of sequences
5+
(often just two sequences). It differs from the longest common substring
6+
problem: unlike substrings, subsequences are not required to occupy
7+
consecutive positions within the original sequences.
8+
9+
## Application
10+
11+
The longest common subsequence problem is a classic computer science
12+
problem, the basis of data comparison programs such as the diff utility,
13+
and has applications in bioinformatics. It is also widely used by
14+
revision control systems such as Git for reconciling multiple changes
15+
made to a revision-controlled collection of files.
16+
17+
## Example
18+
19+
- LCS for input Sequences `ABCDGH` and `AEDFHR` is `ADH` of length 3.
20+
- LCS for input Sequences `AGGTAB` and `GXTXAYB` is `GTAB` of length 4.
21+
22+
## References
23+
24+
- [Wikipedia](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem)
25+
- [YouTube](https://www.youtube.com/watch?v=NnD96abizww)

‎src/algorithms/string/longest-common-subsequnce/__test__/longestCommonSubsequnce.test.js‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
import longestCommonSubsequnce from '../longestCommonSubsequnce';
2+
3+
describe('longestCommonSubsequnce', () => {
4+
it('should find longest common subsequence for two strings', () => {
5+
expect(longestCommonSubsequnce('', '')).toBe('');
6+
expect(longestCommonSubsequnce('', 'ABC')).toBe('');
7+
expect(longestCommonSubsequnce('ABC', '')).toBe('');
8+
expect(longestCommonSubsequnce('ABC', 'DEFG')).toBe('');
9+
expect(longestCommonSubsequnce('ABCDGH', 'AEDFHR')).toBe('ADH');
10+
expect(longestCommonSubsequnce('AGGTAB', 'GXTXAYB')).toBe('GTAB');
11+
expect(longestCommonSubsequnce('ABCDAF', 'ACBCF')).toBe('ABCF');
12+
});
13+
});

‎src/algorithms/string/longest-common-subsequnce/longestCommonSubsequnce.js‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
/**
2+
* @param {string} s1
3+
* @param {string} s2
4+
* @return {string}
5+
*/
6+
export default function longestCommonSubsequnce(s1, s2) {
7+
// Init LCS matrix.
8+
const lcsMatrix = Array(s2.length + 1).fill(null).map(() => Array(s1.length + 1).fill(null));
9+
10+
// Fill first row with zeros.
11+
for (let columnIndex = 0; columnIndex <= s1.length; columnIndex += 1) {
12+
lcsMatrix[0][columnIndex] = 0;
13+
}
14+
15+
// Fill first column with zeros.
16+
for (let rowIndex = 0; rowIndex <= s2.length; rowIndex += 1) {
17+
lcsMatrix[rowIndex][0] = 0;
18+
}
19+
20+
// Fill rest of the column that correspond to each of two strings.
21+
for (let rowIndex = 1; rowIndex <= s2.length; rowIndex += 1) {
22+
for (let columnIndex = 1; columnIndex <= s1.length; columnIndex += 1) {
23+
if (s1[columnIndex - 1] === s2[rowIndex - 1]) {
24+
lcsMatrix[rowIndex][columnIndex] = lcsMatrix[rowIndex - 1][columnIndex - 1] + 1;
25+
} else {
26+
lcsMatrix[rowIndex][columnIndex] = Math.max(
27+
lcsMatrix[rowIndex - 1][columnIndex],
28+
lcsMatrix[rowIndex][columnIndex - 1],
29+
);
30+
}
31+
}
32+
}
33+
34+
// Calculate LCS based on LCS matrix.
35+
if (!lcsMatrix[s2.length][s1.length]) {
36+
// If the length of largest common string is zero then return empty string.
37+
return '';
38+
}
39+
40+
let lcs = '';
41+
let columnIndex = s1.length;
42+
let rowIndex = s2.length;
43+
44+
while (columnIndex > 0 || rowIndex > 0) {
45+
if (s1[columnIndex - 1] === s2[rowIndex - 1]) {
46+
// Move by diagonal left-top.
47+
lcs = s1[columnIndex - 1] + lcs;
48+
columnIndex -= 1;
49+
rowIndex -= 1;
50+
} else if (lcsMatrix[rowIndex][columnIndex] === lcsMatrix[rowIndex][columnIndex - 1]) {
51+
// Move left.
52+
columnIndex -= 1;
53+
} else {
54+
// Move up.
55+
rowIndex -= 1;
56+
}
57+
}
58+
59+
return lcs;
60+
}

0 commit comments

Comments
 (0)