-
Notifications
You must be signed in to change notification settings - Fork 0
/
1143--longest-common-subsequence.js
49 lines (43 loc) · 2.56 KB
/
1143--longest-common-subsequence.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
// 1143. Longest Common Subsequence
/**
* @param {string} textForRow
* @param {string} textForColumn
* @return {number}
*/
const longestCommonSubsequence = function (textForRow, textForColumn) {
// imagine both words as a 2D grid
// add additional 1 row and 1 column to the grid that would help us calculate the values of the last column & last row cells with more ease
// as we're going to iterate only one row at a time, and that row is going to refer to only itself or its bottom row, we don't have to create the whole grid actually
// we can have 2 rows, 1 representing the memoized previous row (the row on the bottom of the current row), and 1 representing the current row
// at the end of each iteration, we can update them (current row becomes the bottom row and we create a new row that becomes the current row)
// create the additional row first and label it the bottom row
// notice that we're adding 1 to the length to create the additional column cell too
// assign zero to each cell to assume the max length of a subsequence starting from that cell is zero
let bottomRow = Array(textForColumn.length + 1).fill(0);
// iterate over the text for row from the end
for (let row = textForRow.length - 1; row >= 0; row--) {
// for the currently iterating character, create a new row and assign 0 to each cell
const currentRow = Array(textForColumn.length + 1).fill(0);
// then iterate over each character of the textColumn from the end
for (let column = textForColumn.length - 1; column >= 0; column--) {
// if the current character in the row matches the current character of the column
if (textForRow[row] === textForColumn[column]) {
// its max length of subsequence is equal to one (representing the current character) plus the memoized value of its bottom right diagonal row
currentRow[column] = bottomRow[column + 1] + 1;
} else {
// if they don't match, the max length of the subsequence starting from the current character is equal to whichever's greater of
// the memoized values of its bottom cell and its right cell
currentRow[column] = Math.max(
bottomRow[column],
currentRow[column + 1]
);
}
}
// after we finish iterating over the text for the column, we move up to the next row
// then the current row becomes the bottom row of that row
bottomRow = currentRow;
}
// after the outer loop finishes, the length of the longest common subsequence possible is memoized in the first cell of the row
// return that value
return bottomRow[0];
};