社区首页 >专栏 >2023-07-07：给出两个字符串 str1 和 str2。返回同时以 str1 和 str2 作为子序列的最短字符串。如

2023-07-07：给出两个字符串 str1 和 str2。返回同时以 str1 和 str2 作为子序列的最短字符串。如

福大大架构师每日一题

发布于 2023-07-25 08:45:25

19000

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2023-07-07：给出两个字符串 str1 和 str2。

返回同时以 str1 和 str2 作为子序列的最短字符串。

如果答案不止一个，则可以返回满足条件的任意一个答案。

输入：str1 = "abac", str2 = "cab"。

输出："cabac"。

答案2023-07-07：

大体步骤如下：

1.初始化字符串 str1 和 str2 分别为 "abac" 和 "cab"。

2.创建一个二维数组 dp，其大小为 (n+1) x (m+1)，其中 n 是 str1 的长度，m 是 str2 的长度。

3.使用动态规划来填充 dp 数组。循环遍历 i 从 1 到 n，以及 j 从 1 到 m。

4.在每个循环中，比较 str1[i-1] 和 str2[j-1] 的值：

• 如果它们相等，更新 dp[i][j] 为 dp[i-1][j-1] + 1，表示当前字符能够在最短公共超序列中出现。
• 否则，取 dp[i-1][j] 和 dp[i][j-1] 中的较大值，表示当前字符不能同时出现在最短公共超序列中，需要从其中一个字符串中选择。

5.创建一个长度为 n + m - dp[n][m] 的字符数组 ans，用于存储最短公共超序列。

6.初始化变量 ansi 为 len(ans) - 1，i 为 n，j 为 m。

7.通过回溯 dp 数组，从右下角开始往左上角移动，直到 i 和 j 达到边界 0。

8.如果 dp[i][j] 等于 dp[i-1][j-1] + 1 且 str1[i-1] 等于 str2[j-1]，表示当前字符是在 str1 和 str2 的最短公共超序列中，将其存入 ans 中并将 ansi 减一，同时将 i 和 j 减一。

9.如果 dp[i][j] 等于 dp[i-1][j]，表示当前字符只出现在 str1 中，将其存入 ans 中并将 ansi 减一，同时将 i 减一。

10.如果 dp[i][j] 等于 dp[i][j-1]，表示当前字符只出现在 str2 中，将其存入 ans 中并将 ansi 减一，同时将 j 减一。

11.当完成回溯后，若 i 大于 0，将 str1 中剩余的字符存入 ans 中。

12.当完成回溯后，若 j 大于 0，将 str2 中剩余的字符存入 ans 中。

13.将 ans 转换为字符串，并作为结果返回。

14.在 main 函数中调用 shortestCommonSupersequence 函数，并输出结果 "cabac"。

时间复杂度：O(nm)，其中 n 是字符串 str1 的长度，m 是字符串 str2 的长度。

空间复杂度：O(nm)，需要使用一个二维数组 dp 来存储中间结果。

这是使用动态规划（Dynamic Programming）解决字符串相关问题的算法。具体来说，这个算法用于找到两个字符串的最短公共超序列（Shortest Common Supersequence）。最短公共超序列是指包含两个字符串的所有字符，并且是长度最短的序列。通过使用动态规划的方法，可以利用子问题的最优解来构建整体的最优解，从而高效地解决这个问题。

go完整代码如下：

package main

import (
    "fmt"
)

func shortestCommonSupersequence(str1 string, str2 string) string {
    n := len(str1)
    m := len(str2)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            if str1[i-1] == str2[j-1] {
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
            }
        }
    }
    ans := make([]byte, n+m-dp[n][m])
    ansi := len(ans) - 1
    i := n
    j := m
    for i > 0 && j > 0 {
        if dp[i][j] == dp[i-1][j-1]+1 && str1[i-1] == str2[j-1] {
            ans[ansi] = str1[i-1]
            ansi--
            i--
            j--
        } else if dp[i][j] == dp[i-1][j] {
            ans[ansi] = str1[i-1]
            ansi--
            i--
        } else {
            ans[ansi] = str2[j-1]
            ansi--
            j--
        }
    }
    for ; i > 0; i-- {
        ans[ansi] = str1[i-1]
        ansi--
    }
    for ; j > 0; j-- {
        ans[ansi] = str2[j-1]
        ansi--
    }
    return string(ans)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    str1 := "abac"
    str2 := "cab"
    result := shortestCommonSupersequence(str1, str2)
    fmt.Println(result)
}

在这里插入图片描述

rust完整代码如下：

fn shortest_common_supersequence(str1: &str, str2: &str) -> String {
    let s1: Vec<char> = str1.chars().collect();
    let s2: Vec<char> = str2.chars().collect();
    let n = s1.len();
    let m = s2.len();
    let mut dp = vec![vec![0 as i32; m + 1]; n + 1];

    let mut i = 1;

    while i <= n {
        let mut j = 1;
        while j <= m {
            dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            if s1[i - 1] == s2[j - 1] {
                dp[i][j] = dp[i][j].max(dp[i - 1][j - 1] + 1);
            }
            j += 1;
        }
        i += 1;
    }

    let ans_length = n + m - dp[n][m] as usize;
    let mut ans = vec![' '; ans_length];
    let mut ansi = ans_length as i32 - 1;
    let (mut i, mut j) = (n, m);

    while i > 0 && j > 0 {
        if dp[i][j] == dp[i - 1][j - 1] + 1 && str1.chars().nth(i - 1) == str2.chars().nth(j - 1) {
            ans[ansi as usize] = str1.chars().nth(i - 1).unwrap();
            ansi -= 1;
            i -= 1;
            j -= 1;
        } else if dp[i][j] == dp[i - 1][j] {
            ans[ansi as usize] = str1.chars().nth(i - 1).unwrap();
            ansi -= 1;
            i -= 1;
        } else {
            ans[ansi as usize] = str2.chars().nth(j - 1).unwrap();
            ansi -= 1;
            j -= 1;
        }
    }

    while i > 0 {
        ans[ansi as usize] = str1.chars().nth(i - 1).unwrap();
        ansi -= 1;
        i -= 1;
    }

    while j > 0 {
        ans[ansi as usize] = str2.chars().nth(j - 1).unwrap();
        ansi -= 1;
        j -= 1;
    }

    ans.iter().collect()
}

fn main() {
    let str1 = String::from("abac");
    let str2 = String::from("cab");

    let result = shortest_common_supersequence(&str1, &str2);
    println!("{}", result);
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string shortestCommonSupersequence(string str1, string str2) {
    int n = str1.size();
    int m = str2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }

    string ans;
    int i = n;
    int j = m;

    while (i > 0 && j > 0) {
        if (dp[i][j] == dp[i - 1][j - 1] + 1 && str1[i - 1] == str2[j - 1]) {
            ans = str1[i - 1] + ans;
            i--;
            j--;
        }
        else if (dp[i][j] == dp[i - 1][j]) {
            ans = str1[i - 1] + ans;
            i--;
        }
        else {
            ans = str2[j - 1] + ans;
            j--;
        }
    }

    while (i > 0) {
        ans = str1[i - 1] + ans;
        i--;
    }

    while (j > 0) {
        ans = str2[j - 1] + ans;
        j--;
    }

    return ans;
}

int main() {
    string str1 = "abac";
    string str2 = "cab";

    string result = shortestCommonSupersequence(str1, str2);
    cout << result << endl;

    return 0;
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* shortestCommonSupersequence(char* str1, char* str2) {
    int n = strlen(str1);
    int m = strlen(str2);
    int** dp = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)malloc((m + 1) * sizeof(int));
        memset(dp[i], 0, (m + 1) * sizeof(int));
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = (dp[i][j] > dp[i - 1][j - 1] + 1) ? dp[i][j] : dp[i - 1][j - 1] + 1;
            }
        }
    }

    int len = n + m - dp[n][m];
    char* ans = (char*)malloc((len + 1) * sizeof(char));
    ans[len] = '\0';
    int ansi = len - 1;
    int i = n;
    int j = m;

    while (i > 0 && j > 0) {
        if (dp[i][j] == dp[i - 1][j - 1] + 1 && str1[i - 1] == str2[j - 1]) {
            ans[ansi--] = str1[i - 1];
            i--;
            j--;
        }
        else if (dp[i][j] == dp[i - 1][j]) {
            ans[ansi--] = str1[i - 1];
            i--;
        }
        else {
            ans[ansi--] = str2[j - 1];
            j--;
        }
    }

    for (; i > 0; i--) {
        ans[ansi--] = str1[i - 1];
    }
    for (; j > 0; j--) {
        ans[ansi--] = str2[j - 1];
    }

    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);

    return ans;
}

int main() {
    char str1[] = "abac";
    char str2[] = "cab";

    char* result = shortestCommonSupersequence(str1, str2);
    printf("%s\n", result);

    free(result);
    return 0;
}