2023-07-07：給出兩個字符串 str1 和 str2。 返回同時以 str1 和 str2 作為子序列的最
2023-07-07：給出兩個字符串 str1 和 str2。
返回同時以 str1 和 str2 作為子序列的最短字符串。
如果答案不止一個，則可以返回滿足條件的任意一個答案。
輸入：str1 = "abac", str2 = "cab"。
輸出："cabac"。
答案2023-07-07：
大體步驟如下：
1.初始化字符串?str1?和?str2?分別為 "abac" 和 "cab"。
2.創(chuàng)建一個二維數(shù)組?dp，其大小為?(n+1) x (m+1)，其中?n?是?str1?的長度，m?是?str2?的長度。
3.使用動態(tài)規(guī)劃來填充?dp?數(shù)組。循環(huán)遍歷?i?從 1 到?n，以及?j?從 1 到?m。
4.在每個循環(huán)中，比較?str1[i-1]?和?str2[j-1]?的值：
??如果它們相等，更新?
dp[i][j]?為?dp[i-1][j-1] + 1，表示當(dāng)前字符能夠在最短公共超序列中出現(xiàn)。??否則，取?
dp[i-1][j]?和?dp[i][j-1]?中的較大值，表示當(dāng)前字符不能同時出現(xiàn)在最短公共超序列中，需要從其中一個字符串中選擇。
5.創(chuàng)建一個長度為?n + m - dp[n][m]?的字符數(shù)組?ans，用于存儲最短公共超序列。
6.初始化變量?ansi?為?len(ans) - 1，i?為?n，j?為?m。
7.通過回溯?dp?數(shù)組，從右下角開始往左上角移動，直到?i?和?j?達(dá)到邊界 0。
8.如果?dp[i][j]?等于?dp[i-1][j-1] + 1?且?str1[i-1]?等于?str2[j-1]，表示當(dāng)前字符是在?str1?和?str2?的最短公共超序列中，將其存入?ans?中并將?ansi?減一，同時將?i?和?j?減一。
9.如果?dp[i][j]?等于?dp[i-1][j]，表示當(dāng)前字符只出現(xiàn)在?str1?中，將其存入?ans?中并將?ansi?減一，同時將?i?減一。
10.如果?dp[i][j]?等于?dp[i][j-1]，表示當(dāng)前字符只出現(xiàn)在?str2?中，將其存入?ans?中并將?ansi?減一，同時將?j?減一。
11.當(dāng)完成回溯后，若?i?大于 0，將?str1?中剩余的字符存入?ans?中。
12.當(dāng)完成回溯后，若?j?大于 0，將?str2?中剩余的字符存入?ans?中。
13.將?ans?轉(zhuǎn)換為字符串，并作為結(jié)果返回。
14.在?main?函數(shù)中調(diào)用?shortestCommonSupersequence?函數(shù)，并輸出結(jié)果 "cabac"。
時間復(fù)雜度：O(nm)，其中 n 是字符串 str1 的長度，m 是字符串 str2 的長度。
空間復(fù)雜度：O(nm)，需要使用一個二維數(shù)組 dp 來存儲中間結(jié)果。
這是使用動態(tài)規(guī)劃（Dynamic Programming）解決字符串相關(guān)問題的算法。具體來說，這個算法用于找到兩個字符串的最短公共超序列（Shortest Common Supersequence）。最短公共超序列是指包含兩個字符串的所有字符，并且是長度最短的序列。通過使用動態(tài)規(guī)劃的方法，可以利用子問題的最優(yōu)解來構(gòu)建整體的最優(yōu)解，從而高效地解決這個問題。
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++完整代碼如下：
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完整代碼如下：
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;
}
