最長公共子序列 - samwu－IT工程師數位筆記本

文章出處

/*
1. 最長公共子序列（LCS）問題
通過構建表格（二維數組），來求兩個結構的公共部分有奇效。

2. 最長遞增子序列LIS的問題  
設原數組為A  
把原數組遞增排序為A'  
求A和A’的最長公共子序列即可。

動態規劃，綜合上幾步計算出的信息，算出下一步的值。
因此需要維護一存儲空間。   

參考鏈接：
http://blog.csdn.net/github_36487770/article/details/66532403
http://blog.csdn.net/lisonglisonglisong/article/details/41596309
*/

function lstd(stra, strb) {
  var n, i, j;
  var dp = [], lst = [];
  var arr = stra.split("");
  var brr = strb.split("");
  var lena = arr.length;
  var lenb = brr.length;
  var LCSArr = [];

  // 構建二維數組，也就是表格 
  for (i = 0; i < lena + 1; i++) {
    dp[i] = [];
    for (j = 0; j < lenb + 1; j++) {
      if (i == 0 || j == 0) dp[i][j] = 0;
      else if (arr[i] === brr[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; }
      else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); }
    }
  }
  var lst = "";

  // 回溯，獲取公共子序列
  var traceback = function (i, j, lst) {

    while (i > 0 && j > 0) {
      if (arr[i - 1] === brr[j - 1]) {
        lst += arr[i - 1];
        if (lst.length === dp[lena][lenb]) {
          LCSArr.push(lst.split("").reverse().join(""));
        }
        i--; j--;
      }
      else {
        if (dp[i - 1][j] > dp[i][j - 1]) { --i; }
        else if (dp[i - 1][j] < dp[i][j - 1]) { --j; }
        else {
          traceback(i - 1, j, lst);
          traceback(i, j - 1, lst);
          return;   //千萬不要忘了return！！！
        }
      }
    }
  };

  traceback(lena, lenb, lst);
  return {
    length:dp[lena][lenb], //公共子序列的最大長度
    LCS: LCSArr
  }

}
let x = "ABCBDAB";
let y = "BDCABA";

console.log(lstd(x, y).LCS);