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

题意整理

从给定的两个输入序列中找出最长的公共子序列，本题限定了只会有一个最长公共子序列，无需考虑多个的情况，当不存在公共子序列时需返回“-1”。

思路

典型的动态规划问题，暴力穷举可能性太多，时间复杂度高，先使用动态规划求得最长公共子序列的长度，最后再根据长度逆推最长公共子序列。
最长公共子序列LCS有以下性质：

假如s1的最后一个元素与s2的最后一个元素相等，那么s1和s2的LCS就等于：{s1减去最后一个元素}与{s2减去最后一个元素}的LCS再加上s1和s2相等的最后一个元素。
假如s1的最后一个元素与s2的最后一个元素不等，那么S1和S2的LCS就等于：{S1减去最后一个元素}与s2的LCS，{s2减去最后一个元素}与s1的LCS中的长度最大的那个序列。

构建二维动态规划dp数组（(m+1)x(n+1)，m,n分别为s1,s2的长度），dp[i][j]表示序列s1[0]...s[i-1]与序列s2[0]...s2[j]的公共子序列长度，dp数组的转移关系如下：

$dp[i][j] = \begin{cases} 0, & \text{if } i = 0 \text{ or } j=0 \\ dp[i-1][j-1] + 1, & \text{if } i > 0, j>0 \text{ and } s1[i]=s2[j] \\ \max\{dp[i-1][j], dp[i][j-1]\}, & \text{if } i > 0, j>0 \text{ and } s1[i] \neq s2[j] \end{cases}$

方法一

构建dp数组的同时，由于要逆推最大公共子序列，同时维护一个direction数组表示当前位置的最大长度从何处转移来，逆推时只需根据direction回溯即可。

示例

给定输入：s1="1A2C3D4B56", "B1D23A456A"
构建dp数组：
图片说明
根据direction数组回溯：

代码

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int m = s1.length(), n = s2.length(); //获得输入的长度以初始化dp数组
        if (m == 0 || n == 0) //若输入为空，没有LCS，返回-1
            return "-1";
        // dp数组保存到dp[i][j](即是s1[1]...s1[i]与s2[1]...s2[j]的LCS)时的LCS的长度
        //direction数组保存LCS转移的方向，1表示从左方转移，2表示从上方转移来，3表示从左上方转移来
        int dp[m+1][n+1], direction[m+1][n+1];
        for (int i = 0; i <= m; i++){
            dp[i][0] = 0; //初始化第一列为0
            direction[i][0] = 0;
        }
        for (int j = 0; j <= n; j++){
            dp[0][j] = 0; //初始化第一行为0
            direction[0][j] = 0;
            }
        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1; //若s1[i]和s2[j]相等，其值是公共子序列的一部分，LCS长度加1
                    direction[i][j] = 3;
                }
                else {//若不等，当前LCS长度为s1[0]...s1[i-1]和s2[0]...s2[j-1]中LSC长度较大的一个
                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
                    direction[i][j] = dp[i-1][j] > dp[i][j-1] ? 2 : 1;
                }
            }
        }
        if (dp[m][n] == 0) //LCS长度为0
            return "-1";
        string ans;
        for (int i = m, j= n; i > 0 && j > 0; ){//逆序回溯
            if (direction[i][j] == 1)//向左回溯
                j--;
            else if (direction[i][j] == 2)//向上回溯
                i--;
            else{//标识为3，当前位置为LCS成员
                ans += s1[i-1]; 
                i--, j--;
            }
        }
        reverse(ans.begin(), ans.end());//回溯为逆序，返回正确结果时进行翻转
        return ans;
    }
};

复杂度分析

时间复杂度：构建dp数组和direction数组复杂度为 $O(mn)$ ,逆推最长公共子序列复杂度为 $O(m+n)$ ，总的复杂度为 $O(mn)$
空间复杂度：构建dp数组和direction数组的空间花费， $O(mn)$

方法二

方法一中依据direction数组进行逆推，实际上依据dp数组也可以直接逆推以节省空间开销。
使用dp数组进行回溯时规则如下：

若当前位置上方和左方LCS长度都不等，则往LCS长度大的方向回溯
若当前位置上方和左方LCS长度都相等，往左上角回溯,且若当前位置s1[i-1]=s2[j-1]，则当前位置为LCS成员

示例

给定输入：s1="1A2C3D4B56", "B1D23A456A"
根据dp数组回溯：
图片说明

代码

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int m = s1.length(), n = s2.length(); //获得输入的长度以初始化dp数组
        if (m == 0 || n == 0) //若输入为空，没有LCS，返回-1
            return "-1";
        int dp[m+1][n+1];// dp数组保存到dp[i][j](即是s1[1]...s1[i]与s2[1]...s2[j]的LCS)时的LCS的长度
        for (int i = 0; i <= m; i++)
            dp[i][0] = 0; //初始化第一列为0
        for (int j = 0; j <= n; j++)
            dp[0][j] = 0; //初始化第一行为0
        for (int i = 1; i <= m; i++){
            for (int j = 1; j <= n; j++){
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1; //若s1[i]和s2[j]相等，其值是公共子序列的一部分，LCS长度加1
                }
                else //若不等，当前LCS长度为s1[0]...s1[i-1]和s2[0]...s2[j-1]中LSC长度较大的一个
                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
            }
        }
        if (dp[m][n] == 0) //LCS长度为0
            return "-1";
        string ans;
        for (int i = m, j= n; i > 0 && j > 0; ){
            if (dp[i][j-1] == dp[i-1][j]){
                if (s1[i-1] == s2[j-1])
                    ans += s1[i-1]; //若当前位置s1[i-1]=s2[j-1]，则当前位置为LCS成员
                i--, j--; //若当前位置上方和左方LCS长度都相等，往左上角回溯;
            }
            else {
                if (dp[i][j-1] > dp[i-1][j])// 若当前位置上方和左方LCS长度都不等，则往LCS长度大的方向回溯
                    j--;
                else
                    i--;
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

复杂度分析

时间复杂度：构建dp数组的复杂度为 $O(mn)$ ,逆推最长公共子序列复杂度为 $O(m+n)$ ，总的复杂度为 $O(mn)$
空间复杂度：构建dp数组的空间花费， $O(mn)$