题解 | #65.最长公共子序列(二)#

这道题我只写出了最长公共子序列的长度，公共子序列实际是什么参考了题解

dp是一个二维数组，行数为s1的长度，列数为s2的长度，首先对与dp[0][]和dp[][0]赋值为0或1，代码的9-15行

状态转移方程：

• s1[pi] == s2[j]------>dp[i][j] = dp[i-1][j-1] + 1;
• s1[pi] != s2[j]------>dp[i][j] = Math.max( dp[i-1][j],dp[i][j-1] )；

想获得公共子序列，参考下图即可，注意如果dp[i][j]=0即可跳出循环，同时要满足i>=0和j>=0

注意：第32行需要i==0也可以，因为如果i=0的时候 dp[i-1]非法，所以需要i==0

function LCS( s1 ,  s2 ) {
  if(s1.length == 0 || s2.length==0)  return -1;
  let dp = [];
  for(let i=0; i<s1.length; i++)
    dp.push([]);
  
  //dp[i][j]表示s1的i 和 s2的j的最长公共子序列
  
  let index = s2.indexOf(s1[0]);
  for(let i=0; i<s2.length; i++)
    dp[0][i] = (i>=index && index!=-1) ? 1:0;
  
  index = s1.indexOf(s2[0]);
  for(let i=0; i<s1.length; i++)
    dp[i][0] = (i>=index && index!=-1) ? 1:0;
  
  for(let i=1; i<s1.length; i++){
    for(let j=1; j<s2.length; j++){
      if(s1[i] == s2[j])
        dp[i][j] = dp[i-1][j-1] + 1;
      else
        dp[i][j] = Math.max( dp[i-1][j],dp[i][j-1] );
    }
  }
  
  let res = [];
  for(let i=s1.length-1,j=s2.length-1; i>=0 && j>=0 && dp[i][j]>=1; ){
    if(s1[i] == s2[j]){
      res.push(s1[i]);
      i--;
      j--;
    }else if(i==0 || dp[i][j-1] > dp[i-1][j]){
      j--;
    }else{
      i--;
    }
  }
  if(res.length==0)  return "-1";
  return res.reverse().join('');
}