forked from trekhleb/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
longestCommonSubsequence.js
60 lines (53 loc) · 1.81 KB
/
longestCommonSubsequence.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
* @param {string[]} set1
* @param {string[]} set2
* @return {string[]}
*/
export default function longestCommonSubsequence(set1, set2) {
// Init LCS matrix.
const lcsMatrix = Array(set2.length + 1).fill(null).map(() => Array(set1.length + 1).fill(null));
// Fill first row with zeros.
for (let columnIndex = 0; columnIndex <= set1.length; columnIndex += 1) {
lcsMatrix[0][columnIndex] = 0;
}
// Fill first column with zeros.
for (let rowIndex = 0; rowIndex <= set2.length; rowIndex += 1) {
lcsMatrix[rowIndex][0] = 0;
}
// Fill rest of the column that correspond to each of two strings.
for (let rowIndex = 1; rowIndex <= set2.length; rowIndex += 1) {
for (let columnIndex = 1; columnIndex <= set1.length; columnIndex += 1) {
if (set1[columnIndex - 1] === set2[rowIndex - 1]) {
lcsMatrix[rowIndex][columnIndex] = lcsMatrix[rowIndex - 1][columnIndex - 1] + 1;
} else {
lcsMatrix[rowIndex][columnIndex] = Math.max(
lcsMatrix[rowIndex - 1][columnIndex],
lcsMatrix[rowIndex][columnIndex - 1],
);
}
}
}
// Calculate LCS based on LCS matrix.
if (!lcsMatrix[set2.length][set1.length]) {
// If the length of largest common string is zero then return empty string.
return [''];
}
const longestSequence = [];
let columnIndex = set1.length;
let rowIndex = set2.length;
while (columnIndex > 0 || rowIndex > 0) {
if (set1[columnIndex - 1] === set2[rowIndex - 1]) {
// Move by diagonal left-top.
longestSequence.unshift(set1[columnIndex - 1]);
columnIndex -= 1;
rowIndex -= 1;
} else if (lcsMatrix[rowIndex][columnIndex] === lcsMatrix[rowIndex][columnIndex - 1]) {
// Move left.
columnIndex -= 1;
} else {
// Move up.
rowIndex -= 1;
}
}
return longestSequence;
}