LeetCode | 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 都由小写英文字母组成。

注意:子序列和子串是不同的概念

思路:分两个步骤
 1. 利用动态规划求最短公共超序列的长度,并保留求解过程
 2. 利用动态规划的求解过程,反推字符串

步骤1:
 设字符串的长度为 m 和 n; dp[i][j] 表示字符串 str1[0, i - 1] 和 str2[0, j - 1] 的最短公共超序列的长度, i 和 j 等于 0 时,表示字符串为空。
求最短公共超序列时,遍历两个字符串,对于 str1[i] 和 str2[j] 只有三种可能的情况:
 1. str1[i] == str2[j], 两个字符一样,加入超序列
 2. str1[i] != str2[j], 两个字符不一样,可能是 str1[i] 加入超序列,也可能是 str2[j] 加入超序列, 因为是求最短的,选择小的加入

 动态规划的状态转移方程为:
 当 str1[i] == str2[j] 时:
     $dp[i][j] = dp[i - 1][j - 1] + 1$
 当 str1[i] != str2[j] 时:
     $dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1$
 边界条件:当 i 或 j 等于 0 时,字符串为空,最短公共超序列等于另一个字符串的长度

dp[i][j]={mj,i=n&j<mni,j=m&i<n0,i=n&j=m

步骤2:
经过步骤1 得到的 dp[m][n] 就是最短公共超序列的长度; 设 t1 = m, t2 = n, 从字符串的尾部开始往前遍历
 如果 str1[t1 - 1] == str2[t2 - 1] 这个字符是共有的,加入到 res。
 如果 str1[t1 - 1] != str2[t2 - 1], 则根据 dp[t1][t2] 是等于 dp[t1 - 1][t2] + 1 还是等于 dp[t1][t2 - 1] + 1 来判断上一个字符是 str1 的字符还是 str2 的字符

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++) { 
        dp[i][0] = i; //当 str2 为空时,最短公共超序列长度为 str1[0, i - 1].size()
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = j; //当 str1 为空时,最短公共超序列长度为 str2[0, j - 1].size()
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    string res;
    int t1 = m, t2 = n;
    // 利用动态规划的求解过程,逆推字符串
    while (t1 > 0 && t2 > 0) {
        if (str1[t1 - 1] == str2[t2 - 1]) {
            res = str1[--t1] + res;
            --t2;
        } else if (dp[t1][t2] == dp[t1 - 1][t2] + 1) {
            res = str1[--t1] + res;
        } else {
            res = str2[--t2] + res;
        }
    }
    if (t1 > 0) {
        res = str1.substr(0, t1) + res;
    }
    if (t2 > 0) {
        res = str2.substr(0, t2) + res;
    }
    return res;
}

和上面一个思路,只是遍历字符串的顺序变了。在求最短公共超序列长度时,这个是从后往前遍历,dp[0][0] 代表的是最短公共超序列长度

string shortestCommonSupersequence(string str1, string str2) {
    int n = str1.size(), m = str2.size();
    // 动态规划求最短公共超序列的长度,并保留求解过程
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i < n; ++i) {
        dp[i][m] = n - i;
    }
    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[i] == str2[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
            } else {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + 1;
            }
        }
    }
    string res;
    int t1 = 0, t2 = 0;
    // 利用动态规划的求解过程,逆推字符串
    while (t1 < n && t2 < m) {
        if (str1[t1] == str2[t2]) {
            res += str1[t1];
            ++t1;
            ++t2;
        } else if (dp[t1 + 1][t2] == dp[t1][t2] - 1) {
            res += str1[t1];
            ++t1;
        } else if (dp[t1][t2 + 1] == dp[t1][t2] - 1) {
            res += str2[t2];
            ++t2;
        }
    }
    if (t1 < n) {
        res += str1.substr(t1);
    }
    else if (t2 < m) {
        res += str2.substr(t2);
    }
    return res;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇