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

 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */
function LCS( s1 ,  s2 ) {
    // write code here
    let sum=''
    let res2=[]
    if(s1.length==0||s2.length==0){return -1;}
    for(let i=0;i<=s2.length;i++){
        let res=[]
        for(let j=0;j<=s1.length;j++){
            if(i==0){res.push(0)}
            else{
                if(j==0){res.push(0)}
                else{
                    if(s1[j-1]==s2[i-1]){
                        res.push(Math.min(res[j-1],res2[i-1][j])+1)
                    }////////min!!!!!!!!
                    //构建矩阵时，想要加，取小的加一
                    else{
                        res.push(Math.max(res[j-1],res2[i-1][j]))
                        //不加时保存大的
                     }
               }
            }
        }
        res2.push(res)
    }
    let m=s2.length
    let n=s1.length
    let ss=res2[s2.length][s1.length]
    for(let i=0;i<ss;i++){
    //从后往前，确保都取得到
        while(res2[m][n]==ss-i){
            while(res2[m][n]==ss-i){
            m--;
            }
            m++;
            while(res2[m][n]==ss-i){
            n--;
            }
            sum=sum+s2[m-1]
        }
        m--;
    }
    let sum2=''
    for(let i=0;i<sum.length;i++){
        sum2=sum2+sum[sum.length-1-i]
    }
    if(sum2.length==0){return -1}
   else{return sum2}
}
module.exports = {
    LCS : LCS
};