forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
longestCommonSubstring.js
66 lines (56 loc) · 2.19 KB
/
longestCommonSubstring.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
61
62
63
64
65
66
/**
* @param {string} string1
* @param {string} string2
* @return {string}
*/
export default function longestCommonSubstring(string1, string2) {
// Convert strings to arrays to treat unicode symbols length correctly.
// For example:
// '𐌵'.length === 2
// [...'𐌵'].length === 1
const s1 = [...string1];
const s2 = [...string2];
// Init the matrix of all substring lengths to use Dynamic Programming approach.
const substringMatrix = Array(s2.length + 1).fill(null).map(() => {
return Array(s1.length + 1).fill(null);
});
// Fill the first row and first column with zeros to provide initial values.
for (let columnIndex = 0; columnIndex <= s1.length; columnIndex += 1) {
substringMatrix[0][columnIndex] = 0;
}
for (let rowIndex = 0; rowIndex <= s2.length; rowIndex += 1) {
substringMatrix[rowIndex][0] = 0;
}
// Build the matrix of all substring lengths to use Dynamic Programming approach.
let longestSubstringLength = 0;
let longestSubstringColumn = 0;
let longestSubstringRow = 0;
for (let rowIndex = 1; rowIndex <= s2.length; rowIndex += 1) {
for (let columnIndex = 1; columnIndex <= s1.length; columnIndex += 1) {
if (s1[columnIndex - 1] === s2[rowIndex - 1]) {
substringMatrix[rowIndex][columnIndex] = substringMatrix[rowIndex - 1][columnIndex - 1] + 1;
} else {
substringMatrix[rowIndex][columnIndex] = 0;
}
// Try to find the biggest length of all common substring lengths
// and to memorize its last character position (indices)
if (substringMatrix[rowIndex][columnIndex] > longestSubstringLength) {
longestSubstringLength = substringMatrix[rowIndex][columnIndex];
longestSubstringColumn = columnIndex;
longestSubstringRow = rowIndex;
}
}
}
if (longestSubstringLength === 0) {
// Longest common substring has not been found.
return '';
}
// Detect the longest substring from the matrix.
let longestSubstring = '';
while (substringMatrix[longestSubstringRow][longestSubstringColumn] > 0) {
longestSubstring = s1[longestSubstringColumn - 1] + longestSubstring;
longestSubstringRow -= 1;
longestSubstringColumn -= 1;
}
return longestSubstring;
}