 # Untitled

a guest
Dec 29th, 2019
135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. let findLength = function (a, b) {
2.     if (a.length === 0 || b.length === 0) {
3.         return 0;
4.     }
5.
6.     // create our dynamic programming grid, which will cache our subproblem answers
7.     let cache = [];
8.     for (let row = 0; row < a.length + 1; row++) { // +1's are for empty string. We need the empty string row/col as a base case
9.         cache.push(new Array(b.length + 1).fill(0));
10.     }
11.
12.     let max = 0;
13.     for (let row = 0; row < a.length + 1; row++) {
14.         for (let col = 0; col < b.length + 1; col++) {
15.             // base case, empty sets being solved against each other.
16.             if (row === 0 || col === 0) {
17.                 cache[row][col] = 0;
18.             } else if (b[row - 1] === a[col - 1]) { // Match! The two numbers are equal.
19.                 // the answer for this subset will be 1 + the subproblem answer for this cell is one above, and to the left, of the current cell.
20.                 cache[row][col] = 1 + cache[row - 1][col - 1];
21.                 // we have a new answer, compare it against our current max
22.                 max = Math.max(max, cache[row][col]);
23.             }
24.         }
25.     }
26.
27.     return max;
28. };