最短公共超序列

题目

1092. 最短公共超序列

---

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。

如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。

示例 1：

输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。

示例 2：

输入：str1 = "aaaaaaaa", str2 = "aaaaaaaa"
输出："aaaaaaaa"

提示：

• 1 <= str1.length, str2.length <= 1000
• str1 和 str2 都由小写英文字母组成。

题解

方法一：

思路

类似LCS的动态规划

令$f_{i,j}$ 为str1的前i个数和str2的前j个数的最短公共超序列长度。

当$str1_i == str2_j$时，$f_{i,j} = f_{i-1,j-1}+1$

否则，$f_{i,j} = min(f_{i,j-1},f_{i-1,j})+1$

然后根据$f$的状态转移逆推构造出最短公共超序列。

令$ans_{i,j}$ 为str1的前i个数和str2的前j个数的最短公共超序列。

当$str1_i == str2_j$时，$ans_{i,j} = ans_{i-1,j-1}+str1_i$
否则，$\begin{array}{ll} ans_{i,j} = ans_{i-1,j}+str1_i & f_{i-1, j}<f_{i,j-1} \ ans_{i,j} = ans_{i,j-1}+str2_j & f_{i-1, j}\ge f_{i,j-1}\end{array}$

代码

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        @cache
        def dfs(l:int, r:int)->int:
            if l<0 : return r+1
            if r<0 : return l+1
            if str1[l] == str2[r] : return dfs(l-1, r-1)+1
            return min(dfs(l-1, r), dfs(l, r-1))+1
        
        def ans(l:int, r:int)->str:
            if l<0 : return str2[:r+1]
            if r<0 : return str1[:l+1]
            if str1[l] == str2[r] : return ans(l-1, r-1)+str1[l]
            elif dfs(l, r-1) > dfs(l-1, r) : return ans(l-1, r)+str1[l]
            else : return ans(l, r-1)+str2[r]
        return ans(len(str1)-1, len(str2)-1)

方法二：

思路

先求str1和str2的最长公共子序列长度k。

可知sz1+sz2-k是最终构造出来的串的长度。sz1为str1长度，sz2为str2长度。

求最长公共子序列，令dp[i][j]为str1的前i个字符和str2的前j个字符的最长公共子序列长度。

当str1[i-1] != str2[j-1] 时，dp[i][j] = max(dp[l-1][r], dp[l][r-1])

当str1[i-1] != str2[j-1] 时，dp[i][j] = dp[l-1][r-1]+1

构造字符串。

首先初始化双指针i=sz1, j=sz2

当str1[i-1] == str2[j-1]时, 说明找到了公共字符加入字符串中。

否则，判断dp[i-1][j] 和 dp[i][j-1]谁更大就移动对应的i和j指针，并加入所指向字符到字符串。每次选择大的dp值来移动指针可以确保选出k个公共字符。

代码

class Solution {
public:
    string s1, s2;
    int dp[1004][1004];
    int dfs(int l, int r) {
        if (l == 0 || r == 0) return dp[l][r] = 0;
        if (dp[l][r]) return dp[l][r];
        dp[l][r] = max(dfs(l-1, r), dfs(l, r-1));
        if (s1[l-1] == s2[r-1]) dp[l][r] = max(dp[l][r], dfs(l-1, r-1)+1);
        return dp[l][r];
    }
    string shortestCommonSupersequence(string str1, string str2) {
        int sz1 = str1.size(), sz2 = str2.size();
        s1 = str1;
        s2 = str2;
        // dfs(sz1, sz2);
        for (int i=1; i<=sz1; i++) {
            for (int j=1; j<=sz2; j++) {
                if (str1[i-1] == str2[j-1]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        // for (int i=1; i<=sz1; i++) {
        //     for (int j=1; j<=sz2; j++) {
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << "\n";
        // }
        int l = sz1, r = sz2;
        string rt;
        while (dp[l][r] > 0) {
            if (str1[l-1] == str2[r-1]) {
                rt.push_back(str2[r-1]);
                r--; l--;
            } else if (dp[l-1][r] > dp[l][r-1]){
                rt.push_back(str1[--l]);
            } else {
                rt.push_back(str2[--r]);
            }
        }
        while (l>0) rt.push_back(str1[--l]);
        while (r>0) rt.push_back(str2[--r]);
        reverse(rt.begin(), rt.end());
        return rt;
    }
};