网站 建设 标准方案,电脑公司网站模板,wordpress 仿简书,云南文山三七给你两个字符串 str1 和 str2#xff0c;返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个#xff0c;则可以返回满足条件的 任意一个 答案。
如果从字符串 t 中删除一些字符#xff08;也可能不删除#xff09;#xff0c;可以得到字符串 s #x…给你两个字符串 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();vectorvectorint dp(m1, vectorint(n1));for (int i 1; i m; i) {for (int j 1; j n; j) {if (str1[i - 1] str2[j - 1]) {// 如果当前字符相等则在前一个 LCS 的基础上加 1dp[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 数组来构建resultwhile (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。
