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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */
function LCS(s1, s2) {
    // write code here
    // 设置一个 s1.length * s2.length 的数组dp，从左上开始
    // 记录s1的前i个字符与s2的前j个字符的最大子序列
    // 状态方程是
    // if(s1[1]==s2[i]){dp[i][j] = dp[i-1],[j-1]+1}
    // else{ dp[i][j] = Math.max(dp[i-1],[j],dp[i],[j-1])}
    if(s1.length==0 || s2.length==0) return-1
    let dp = [];
    for (let i = 0; i < s1.length; i++) {
        dp.push([]);
        for (let j = 0; j < s2.length; j++) {
            if (s1[i] == s2[j]) {
                if (i == 0 || j == 0) {
                    dp[i][j] = ""+s1[i];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + s1[i];
                }
            } else {
                if(i == 0&& j == 0){
                    dp[i][j] = ""
                }
                else if (i == 0) {
                    dp[i][j] = dp[i][j - 1]
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j]
                } else {
                    dp[i][j] = dp[i - 1][j].length>dp[i][j - 1].length?dp[i - 1][j]:dp[i][j - 1];
                }
            }
        }

        
    }
        return dp[s1.length-1][s2.length-1].length ==0?-1:dp[s1.length-1][s2.length-1]
}
module.exports = {
    LCS: LCS,
};