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] 的值：
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;}
复制代码
评论