# 1092. Shortest Common Supersequence
###### tags: `Leetcode` `Hard` `Dynamic Programming` `LCS`
Link: https://leetcode.com/problems/shortest-common-supersequence/
## 思路
先解决一个最长公共子串问题（LCS），求得二维数组```dp[i][j]```，然后根据这个dp的定义来重构超级串。

同样，我们逆序构造这个超级串：

如果```dp[i][j]```是由```dp[i-1][j-1]+1```得来,也即是说```str1[i]==str2[j]```，那么就意味着当时在构建SCS的时候，是在```dp[i-1][j-1]```的基础上加上```str1[i]```(或者```str2[j]```).
如果```dp[i][j]```是由```dp[i-1][j]```得来,也即是说```str1[i]```不是属于这个LCS的一部分，那么现在构造SCS的时候，先把它加上。
如果```dp[i][j]```是由```dp[i][j-1]```得来,也即是说```str2[j]```不是属于这个LCS的一部分，那么现在构造SCS的时候，先把它加上。
## Code

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int p1 = m-1, p2 = n-1;
        while(p1>=0 && p2>=0){
            if(str1.charAt(p1)==str2.charAt(p2)){
                sb.append(str1.charAt(p1));
                p1--;
                p2--;
            }
            else if(dp[p1+1][p2+1]==dp[p1][p2+1]){
                sb.append(str1.charAt(p1));
                p1--;
            }
            else{
                sb.append(str2.charAt(p2));
                p2--;
            }
        }
        while(p1>=0){
            sb.append(str1.charAt(p1));
            p1--;
        }
        while(p2>=0){
            sb.append(str2.charAt(p2));
            p2--;
        }
        return sb.reverse().toString();
    }
}