## 解题思路
- 找到str1和str2的最长公共子序列
- 把str1和str2独有的字符加入进来

## 代码
~~~java
class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int L1 = str1.length();
        int L2 = str2.length();
        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();
        int[][] dp = new int[L1 + 1][L2 + 1];
        for(int i = 1; i <= L1; i++) {
            for(int j = 1; j <= L2; j++) {
                if(c1[i - 1] == c2[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 sbr = new StringBuilder();
        int i = L1;
        int j = L2;
        while(i > 0 || j > 0) {
            if(i == 0) {
                sbr.append(c2[j - 1]);
                j--;
            }
            else if(j == 0) {
                sbr.append(c1[i - 1]);
                i--;
            }
            else {
                if(c1[i - 1] == c2[j - 1]) {
                    sbr.append(c2[j - 1]);
                    i--;
                    j--;
                }
                else if(dp[i][j] == dp[i - 1][j]) {
                    sbr.append(c1[i - 1]);
                    i--;
                }
                else if(dp[i][j] == dp[i][j - 1]) {
                    sbr.append(c2[j - 1]);
                    j--;
                }
            }
        }
        return sbr.reverse().toString();
    }
}
~~~

1092. 最短公共超序列

目录