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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */
function LCS( s1 ,  s2 ) {
    // write code here
    const m = s1.length
    const n = s2.length
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    
    for (let i = 0; i<m; i++) {
        for (let j = 0; j<n; j++) {
            if (s1.charAt(i) === s2.charAt(j)) {
                dp[i+1][j+1] = dp[i][j] + 1
            }
            else {
                dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
            }
        }
    }

    if (dp[m][n] === 0) {
        return -1
    }

    let i = m
    let j = n
    let LcsStr = ''
    while( i>0 && j>0) {
        if (s1.charAt(i-1) === s2.charAt(j-1)) {
            LcsStr = s1.charAt(i-1) + LcsStr
            i--
            j--
        }
        else if (dp[i][j-1] > dp[i-1][j-1]) {
            j--
        }
        else {
            i--
        }
    }
    return LcsStr
}
module.exports = {
    LCS : LCS
};