当前位置: 首页 > article >正文

【动态规划-最长公共子序列(LCS)】【hard】力扣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 都由小写英文字母组成。

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int m = str1.size(), n = str2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    // 如果当前字符相等,则在前一个 LCS 的基础上加 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 否则,取前一个状态的最大值
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        int i = str1.size();
        int j = str2.size();
        string result = "";

        // 通过回溯 dp 数组来构建result
        while (i > 0 && j > 0) {
            if (str1[i - 1] == str2[j - 1]) {
                // 如果字符相等,则是 result 的一部分
                result = str1[i - 1] + result;
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                // 如果字符不等,加入 str1 的字符
                result = str1[i - 1] + result;
                i--;
            } else {
                // 或者加入 str2 的字符
                result = str2[j - 1] + result;
                j--;
            }
        }

        while (i > 0) {
            result = str1[i - 1] + result;
            i--;
        }
        while (j > 0) {
            result = str2[j - 1] + result;
            j--;
        }
        return result;
    }
};

时间复杂度:O(n×m)
空间复杂度:O(n×m)

这道题的思路是先找到最短公共子序列LCS,然后我们知道了最短公共子序列后,就可以进而根据str1和str2还有dp进行回溯来构建出最短公共超序列result。

这道题的前面部分就是在求关于LCS的dp数组,可以参考模板力扣1143(主页有)。
这道题的难点我觉得是在回溯dp来构建result上面。
根据题目给的例子:

我们定义两个指针i和j分别指向str1和str2的最后一个元素。
当两个元素相等的时候,说明他们是LCS的一部分,所以将这个元素推入result中,由于str1和str2都包含这个元素,所以i和j都要-1。
当两个元素不相等的时候,我们就要将较不容易影响LCS的字符推入到result中,比如dp[i - 1][j] > dp[i][j - 1],也就是str[i-1]相对str[j-1]从字符串推入到result后,能尽可能保证剩下的字符串的LCS尽可能的大。

举个例子:
输入:str1 = “abac”, str2 = “cab”
在第一次判断的过程中,指针i指向str1的c,指针j指向str2的b,由于str1和str2的LCS是ab,那么b作为LCS的一部分,那么推入b就会影响到LCS(如果推入b后,那么构造LCS就没有意义,构造LCS的目的是让指针在都指向LCS的部分的时候,可以只推入一个元素,然后同时让i和j都-1)。所以我们推入c到result。


然后我们还要处理剩余部分,当某个字符串遍历完后,那么还会有一个字符串没有将元素推入到result中,这时候我们遍历完这个没遍历完的字符串,将其剩余部分推入result。


http://www.kler.cn/news/339403.html

相关文章:

  • 独家揭秘!成为CSDN人工智能优质创作者:我的故事和心得
  • Redis-消息队列
  • JavaScript 变量的简单学习
  • 贪心算法c++
  • docker compose入门3—docker compose yaml字段详解
  • Polars:从 Apache Spark 过渡指南
  • 探索杨辉三角形的奥秘:C#实现
  • Python | Leetcode Python题解之第464题我能赢吗
  • 【什么是回调机制?一篇文章掌握回调机制及思想】
  • 在虚拟机里试用了几个linux操作系统
  • 网络编程(14)——基于单例模板实现的逻辑层
  • 收银台实现iframe跨页面调用函数的方法——未来之窗行业应用跨平台架构
  • 《系统架构设计师教程(第2版)》第17章-通信系统架构设计理论与实践-07-通信网络构建案例分析
  • 毕设 深度学习语义分割实现弹幕防遮(源码分享)
  • 容器管理工具Docker
  • List子接口
  • C语言 | 第十一章 | static 日期函数 数学函数
  • 活动邀请 | SonarQube×创实信息即将亮相2024 GOPS全球运维大会-上海站,分享代码质量与安全提升策略
  • JavaScript函数基础(通俗易懂篇)
  • 【iOS】计算器仿写