21 Longest common subsequence in JavaScript

lcs.js

var str1 = "XMJYAUZ";
var str2 = "MZJAWXU";
var result = lcs(str1, str2);
console.log(result);

// result is { maxLength: 4, sequence: 'MJAU' }

function lcs(str1, str2){
  var maxLength = 0, maxCol = 0, maxRow = 0;
  var sequence = "";
  var firstRow = new Array(str1.length + 1);
  firstRow.fill(0);
  var grid = [firstRow];
  for (var i = 0; i < str2.length; i++) {
    var row = [0];
    for (var j = 0; j < str1.length; j++) {
      var leftTop = grid[i][j];
      var top = grid[i][j + 1];
      var left = row[j];
      var result;
      if(str1[j] == str2[i]){
        result = leftTop + 1;
      }else{
        result = Math.max(top, left);
      }
      if(result > maxLength){
        maxLength = result;
        maxRow = i + 1;
        maxCol = j + 1;
      }
      row.push(result);
    }
    grid.push(row);
  }

  // backtrack to get the longest current sequence
  sequence = backtrack(maxRow, maxCol, "");

  return {
    maxLength, sequence
  }
  
  function backtrack(row, col, tempString){
    if(row == 0 || col == 0){
      return tempString;
    }else{
      var current = grid[row][col];
      var left = grid[row][col - 1];
      var top = grid[row - 1][col];
      if(current == left){
        return backtrack(row, col - 1, tempString);
      }else if(current == top){
        return backtrack(row - 1, col, tempString);
      }else{
        tempString = str2[row - 1] + tempString;
        return backtrack(row - 1, col - 1, tempString);
      }
    }
  }
}