oreillymedia / data_structures_and_algorithms_using_javascript

768 stars 407 forks source link

Chap14-2.js : 'haven' and 'havoc' wrong answer #20

Open tbswang opened 5 years ago

tbswang commented 5 years ago

for the first char in a string , it could be equal.

function longestSubString(a, b) {
  var arr = [];
  for (var i = 0; i < a.length; i++) {
    arr[i] = [];
    for (var j = 0; j < b.length; j++) {
      arr[i][j] = 0;
    }
  }

  var max = 0;
  var index = 0;
  for (var i = 0; i < a.length; i++) {
    for (var j = 0; j < b.length; j++) {
      //for boundary element 
      if (i === 0 || j === 0) {
        if (a[i] === b[j]) {
          arr[i][j] = 1;
          max = 1;
        } else {
          arr[i][j] = 0;
        }
      } else {
        if (a[i] === b[j]) {
          arr[i][j] = arr[i - 1][j - 1] + 1;
        } else {
          arr[i][j] = 0;
        }
      }
      if (max < arr[i][j]) { 
        max = arr[i][j]; 
        index = i;
      }
    }
  }

  var str = "";
  if (max == 0) {
    return "";
  }
  else {
    for (var i = index+1 - max; i <= index; ++i) {
      str += a[i];
    }
    return str;
  }
}