LeetCode每日一题（2023/3/28）

1092. 最短公共超序列

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

（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）

示例：

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

提示：

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

解答：

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        // 创建一个二维数组来存储子串的最短公共超序列的长度
        int[][] dp = new int[n + 1][m + 1];
        
        // 初始化 dp 数组的最后一列
        for (int i = 0; i < n; ++i) {
            dp[i][m] = n - i;
        }
        
        // 初始化 dp 数组的最后一行
        for (int i = 0; i < m; ++i) {
            dp[n][i] = m - i;
        }
        
        // 从后向前遍历两个字符串，计算子串的最短公共超序列的长度
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                if (str1.charAt(i) == str2.charAt(j)) {
                    // 如果当前字符相同，则子串的最短公共超序列的长度加 1
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                } else {
                    // 如果当前字符不同，则子串的最短公共超序列的长度是两个子问题中较小的值加 1
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + 1;
                }
            }
        }
        
        // 根据 dp 数组构造最短公共超序列
        StringBuilder res = new StringBuilder();
        int t1 = 0, t2 = 0;
        while (t1 < n && t2 < m) {
            if (str1.charAt(t1) == str2.charAt(t2)) {
                // 如果当前字符相同，则将该字符添加到结果中，同时更新两个字符串的指针
                res.append(str1.charAt(t1));
                ++t1;
                ++t2;
            } else if (dp[t1 + 1][t2] == dp[t1][t2] - 1) {
                // 如果 dp[t1 + 1][t2] == dp[t1][t2] - 1，则说明当前字符在 str2 中没有出现，将该字符添加到结果中，同时更新 str1 的指针
                res.append(str1.charAt(t1));
                ++t1;
            } else if (dp[t1][t2 + 1] == dp[t1][t2] - 1) {
                // 如果 dp[t1][t2 + 1] == dp[t1][t2] - 1，则说明当前字符在 str1 中没有出现，将该字符添加到结果中，同时更新 str2 的指针
                res.append(str2.charAt(t2));
                ++t2;
            }
        }
        
        // 将剩余的字符添加到结果中
        if (t1 < n) {
            res.append(str1.substring(t1));
        } else if (t2 < m) {
            res.append(str2.substring(t2));
        }
        
        return res.toString();
    }
}