Advertisement
Guest User

Untitled

a guest
Dec 29th, 2019
135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
JavaScript 1.15 KB | None
  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. };
Advertisement
RAW Paste Data Copied
Advertisement