最长公共子序列(二)（动态规划）

题意

给定两个字符串,求它们的最长公共序列

思路分析

公共序列

要找s1和s2的公共序列,如果有字符相等s1[i] == s2[j],那么s1[0..i-1]和s2[0..j-1]的公共序列加上相等的字符,就能得到一个更长的公共序列, 所以有, 令s[i][j]表示分别匹配到i,j的一个公共序列

for(int i = 0; i < s1.length();i++){
    for(int j = 0;j < s2.length();j++){
        if(s1[i] == s2[j]){ // 匹配字符
            s[i][j] = s[i-1][j-1] + s1[i]; // 上一个拼接 新字符
        }else{ // 不匹配时
            s[i][j] = s[i][j-1] or s[i-1][j]; // 两个中任选一个
        }
    }
}

最长

上述的方案中,保证了是公共的序列,但是没有控制最长

考虑增加长度的比较,来选择更优长度的s

for(int i = 0; i < s1.length();i++){
    for(int j = 0;j < s2.length();j++){
        if(s1[i] == s2[j]){ // 匹配字符
            if(s[i-1][j-1].length() + 1 > s[i][j].length()){ // 更长
            	s[i][j] = s[i-1][j-1] + s1[i]; // 上一个拼接 新字符
            }
        }else{ // 不匹配时
            if(s[i][j-1].length() > s[i][j].length()){ // 更长
                s[i][j] = s[i][j-1];
            }
            if(s[i-1][j].length() > s[i][j].length()){ // 更长
                s[i][j] = s[i-1][j];
            }
        }
    }
}

s对应的长度表

alt

空间优化

上述方案的缺点是,把字符串复制了一次又一次,总复杂度达到了 $O (n^{3})$

既然只有在s1[i]==s2[j]时才增加字符, 所以考虑, 记录上述每个s的上一个s的坐标, 这样最终需要答案时,直接沿着坐标关系,相等时输出即可

把上面直接记录字符串拆分成长度记录dp,坐标记录pre

dp[i][j] = s[i][j].length()

pre[i][j] = {取值的上一个i,取值的上一个j}

边界处理

这里主要的边界是运算时的边界,所以初始化其中一个长度为0时的dp为零

for(int i = 0;i<=s1.size();i++){ 
    dp[i][0] = 0;
}
for(int i = 0;i<=s2.size();i++){
    dp[0][i] = 0;
}

另一个是未计算过的值,因为要求最大值,所以未计算的值也可以设置成0 即表示长度匹配了零个有实际意义,又能参与比较

综上,直接所有长度默认初始化为0

题解

所以整合上面的内容

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        if(s1.size()*s2.size() == 0)return "-1";
        vector<vector<int> > dp(s1.size()+1,vector<int>(s2.size()+1,0)); // 记录最小值
        vector<vector<pair<int,int> > > pre(
            s1.size()+1,vector<pair<int,int>>(s2.size()+1,make_pair(0,0))); // 记录最小值来源
        for(int i = 0;i < s1.size();i++){
            for(int j = 0;j < s2.size();j++){
                if(s1[i] == s2[j]){ // 相等时
                    if(dp[i][j] + 1 > dp[i+1][j+1]){ // 有更长的值
                        dp[i+1][j+1] = dp[i][j]+1; // 长度
                        pre[i+1][j+1] = {i,j}; // 来源
                    }
                }else{
                    if(dp[i+1][j] > dp[i+1][j+1]){ // 不匹配s2
                        dp[i+1][j+1] = dp[i+1][j]; // 长度
                        pre[i+1][j+1] = {i+1,j}; // 来源
                    }
                    if(dp[i][j+1] > dp[i+1][j+1]){ // 不匹配s1
                        dp[i+1][j+1] = dp[i][j+1]; // 长度
                        pre[i+1][j+1] = {i,j+1}; // 来源
                    }
                }
            }
        }
        if(dp[s1.size()][s2.size()] == 0)return "-1"; // 长度为0
        string res = "";
        int i = s1.size();
        int j = s2.size();
        while(i != 0 && j != 0){ // 重构字符串
            if(s1[i-1] == s2[j-1]) res = s1[i-1] + res; // 相等的位置
            auto [pi,pj] = pre[i][j]; // 上一个i,j
            i = pi;
            j = pj;
        }
        return res;
    }
};

复杂度分析

空间复杂度: 状态数量是两个字符串长度之积，所以空间复杂度为 $O (n^{2})$

时间复杂度: 状态转移代价是常数代价,所以时间复杂度为 $O (n^{2})$

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