题解 | #最长公共子序列-II#

/**
 * 这个没有看别人的解题，自己独立写出来的，因为之前在书里看过相关的例子，但是不太一样，书里的例子只求最长的长度，所以在数组里存数字就行，一开始没看仔细，发现不对，想了一下，就是试着直接存字符，初始化首行首列为“”，然后比较字符，如果相等，当前位置赋值为[i-1][j-1]+当前字符，否则就从[i-1][j]或[i][j-1]取最长的。最后结果就在右下角。后来看别人的解题，很多还是存数字，然后再根据数字取字符，那样就麻烦多了！
 */
function LCS( s1 ,  s2 ) {
    // write code here
    if(typeof s1 != 'string' || typeof s2 != 'string'){
        return -1;
    }
    
    if(s1==''||s2==''){
        return -1;
    }
    const arr=[];
    let m=s1.length;
    let n=s2.length;

    for(let i=0;i<=m;i++){
        if(arr[i]===undefined){
            arr[i]=[];
        }
        for(let j=0;j<=n;j++){
            if(i==0 || j==0){
                arr[i][j]='';
                continue;
            }
            let c1=s1.charAt(i-1);
            let c2=s2.charAt(j-1)
            if(c1==c2){
                arr[i][j]=arr[i-1][j-1]+c1;
            }
            else{
                let l1=arr[i-1][j].length;
                let l2=arr[i][j-1].length;
                arr[i][j]=l1>=l2?arr[i-1][j]:arr[i][j-1];
            }
        }
    }
    
    return arr[m][n]==''?-1:arr[m][n];
}
module.exports = {
    LCS : LCS
};