NC92 最长公共子序列 -II

题解

function LCS( s1 ,  s2 ) {
    let res = []
    let len1 = s1.length
    let len2 = s2.length
    let l1 = len1
    let l2 = len2
    
    if(l1 === 0 || l2 === 0){
        return "-1"
    }
    
    let dp = new Array(len1 + 1)
    for(let i = 0; i < len1 + 1; ++i){
        dp[i] = new Array(len2 + 1).fill(0)
    }
    
    for(let i = 1; i < len1 + 1; ++i){
        for(let j = 1; j < len2 + 1; ++j){
            if(s1[i - 1] == s2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1
            }else{
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
            }
        }
    }
    
    while(l1 && l2){
        if(s1[l1 - 1] === s2[l2 - 1]){
            res.push(s1[l1 - 1])
            --l1
            --l2
        }else{
            if(dp[l1 - 1][l2] > dp[l1][l2 - 1]){
                --l1
            }else if(dp[l1 - 1][l2] < dp[l1][l2 - 1]){
                --l2
            }else{
                --l1
                --l2
            }
        }
    }
    
    if(res.length === 0){
        return "-1"
    }else{
        return res.reverse().join('')
    }
}

解析

初始化二维dp数组

let dp = new Array(len1 + 1)
for(let i = 0; i < len1 + 1; ++i){
    dp[i] = new Array(len2 + 1).fill(0)
}

动态规划的核心部分, dp内保存的是指s1[0] -> s1[i-1]与s2[0] -> s2[j-1]中最长公共序列的长度, 如果当前字符相等，则公共序列长度可以+1

for(let i = 1; i < len1 + 1; ++i){
    for(let j = 1; j < len2 + 1; ++j){
        if(s1[i - 1] == s2[j - 1]){
            dp[i][j] = dp[i - 1][j - 1] + 1
        }else{
            dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
        }
    }
}

反向遍历字符串，如果字符相等，则这两个字符一定在公共序列中（因为dp[i][j] = dp[i - 1][j - 1] + 1）

if(s1[l1 - 1] === s2[l2 - 1]){
    res.push(s1[l1 - 1])
    --l1
    --l2
}

如果字符不相等可以分为三种情况

dp[l1 - 1][l2] > dp[l1][l2 - 1]

1. dp[l1][l2]表示到l1和l2为止，最长的子序列长度。dp[l1 - 1][l2] > dp[l1][l2 - 1]说明不考虑s1[l1-1]与s2[l2-1]时，dp[l1-1][l2]的公共子序列长度>dp[l1][l2 - 1]的子序列长度，即字符s1[l1-1]不在子序列中，该字符的存在没有对dp的值产生影响，可以不考虑。因此–l1

2. 第二种情况同上

3. 如果同时不考虑最后两个字符没有对dp值产生影响，说明这两个字符都不在子序列中（根据循环条件，两个字符一定不相等）