Leetcode 1092. 最短公共超序列（DAY 69） ---- 动态规划学习期（先去二刷了最长自序列后面来做的 hard）

原题题目

代码实现（首刷部分看解部分自解）

class Solution {
    
public:string shortestCommonSupersequence(string str1, string str2) {
    int strl1 = str1.size(),strl2 = str2.size(),i,j;string ret,temp;vector<vector<string>> dp(strl1+1,vector<string>(strl2+1,""));for(i=1;i<=strl1;++i){
    for(j=1;j<=strl2;++j){
    if(str1[i-1] != str2[j-1]){
    if(dp[i-1][j].size() > dp[i][j-1].size())dp[i][j] = dp[i-1][j];else    dp[i][j] = dp[i][j-1];}elsedp[i][j] = dp[i-1][j-1] + str1[i-1];}}temp = dp[strl1][strl2];i=j=0;for(char ch:temp){
    while(i<strl1 && str1[i]!=ch)ret+=str1[i++];while(j<strl2 && str2[j]!=ch)ret+=str2[j++];ret+=ch;++i,++j;}return ret+str1.substr(i)+str2.substr(j);}
};