本题的核心是找到LCS，然后通过dp数组，反向构建出 Common Supersequence。这和 print LCS 的思路极其相似。

class Solution {public:    string shortestCommonSupersequence(string str1, string str2) {        int m=str1.size(), n=str2.size();        vector
     
      
       > dp(m+1, vector
       
        (n+1, 0));        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] = max(dp[i-1][j], dp[i][j-1]);            }        }        int i=m, j=n;        string res="";        while (i>0 || j>0){            if (i==0){                res += str2[--j];            }else if (j==0){                res += str1[--i];            }else if (str1[i-1] == str2[j-1]){                res += str1[i-1];                --i; --j;            }else if (dp[i-1][j] > dp[i][j-1]){                res += str1[--i];            }else{                res += str2[--j];            }        }        reverse(res.begin(),res.end());        return res;    }};
       
      
     

时间复杂度 O(mn)