class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        // dp搜索最长公共子序列 + dp数组逆推还原搜索路径
        // 构造包含str1和str2的最短字符串,可以想到是将str1和str2的公共子序列作为骨架,再将二者非公共序列部分按次序填入骨架中.
        // 而之前用的dp都只是返回两字符串最长公共子序列长度,并没有得到具体子串实体,但是实际上在str1和str2中寻找最长公共子序列的整条搜索路径都存储在dp数组中,搜索时是从dp[1][1]到dp[m][n],每一步都由上一步选择得到,所以在还原搜索路径时可以从dp[m][n]逆向倒推回dp[1][1],所得到的搜索路径上的字符组合起来就是本题所求最短公共超序列.
        // 原理: 在二维dp递推最长公共子序列过程中,是枚举了str1和str2中所有子串对所对应的公共序列长度,从中选择了公共子序列最长的一条路径(dp左上角到右下角),也就是说在到达dp[m][n]的这条路径中,是将str1和str2整个串分别作为子序列去求最长公共子序列,路径中每一步从二者对位选取其中一个字符(对位不同)或将两个相同的对位字符选入最长公共子串,那么这条搜索路径就正好符合题目最短公共超列的要求。
        // 1、包含str1、str2所有字符号。
        // 2、每个字符遍历一次。
        // 2、按原字符串顺序搜索。
        // 再根据路径上每一步与上一步dp值(公共序列长度)关系，可以区分公共序列字符(骨架)与非公共字符，str1、str2中对位的公共序列字符只添加到结果str中一次，其余非公共字符需要按原字符串顺序分别添加进str。
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m+1][n+1];
        // 构建str1、str2最长公共子串搜索树（二维数组）
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                // str1(i)与str2(j)对位相同,二者作为最长公共子序列之一,路径长+1.
                if(str1.charAt(i) == str2.charAt(j)) {dp[i+1][j+1] = dp[i][j] + 1;}
                // str1(i)与str2(j)对位不同时,抛弃二者之一,在抛弃后二字符串剩余前面部分继续寻找公共字符,选择公共路径长度最大的抛弃方案
                // 抛弃str1(i): dp[i+1][j+1] = dp[i][j+1]; 抛弃str2(j): dp[i+1][j+1] = dp[i+1][j];
                else{dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);}
            }
        }
        StringBuffer str = new StringBuffer();
        int i = m, j = n;
        // 根据已获得的dp数组，从最长公共子序列长度dp[m][n]处向前递推最长公共数组的路径(终点为dp[0][0]，也就是i==0 && j==0)。
        while(i > 0 || j > 0){
            // 当i==0时说明str1已经消耗完，将str2的剩余前面部分逐一添加至str后即可。
            if(i == 0){
                str.append(str2.charAt(--j));
            // 当j==0时说明str2已经消耗完，将str1的剩余前面部分逐一添加至str后即可。
            }else if(j == 0){ 
                str.append(str1.charAt(--i));
            // 当i、j都有剩余时，根据dp[i][j]的值及其上方、左侧、左上角的值判断在递推最长公共子序列时上一步是如何选择的，借此还原路径
            }else{
                // 当dp[i][j]==dp[i-1][j]时,说明在寻找最长公共子序列路径中，这一步选择的是str1(i-1),所以将str1(i-1)添加到结果中并将str1上的指针i前移1位。
                if(dp[i][j] == dp[i-1][j]){
                    str.append(str1.charAt(--i));
                // 当dp[i][j]==dp[i][j-1]时,说明在寻找最长公共子序列路径中，这一步选择的是str2(j-1),所以将str2(j-1)添加到结果中并将str2上的指针j前移1位。
                }else if(dp[i][j] == dp[i][j-1]){
                    str.append(str2.charAt(--j));
                // 刨除前两种选择后,说明寻找最长公共子序列路径过程中.这一步一定是两个字符串对位相同,指针同步前移,也就是dp[i][j]==dp[i-1][j-1],那么就将str1(i-1)/str2(j-1)加入结果str末尾,并将两指针同步前移,在二字符串前面部分推算路径下一字符.
                }else{
                    str.append(str1.charAt(--i));
                    --j;
                }
            }
        }
        // 由于是从后向前递推的公共子序列搜索路径,但是结果字符串str是尾插法,所以需要将str反转后转为string输出.
        return str.reverse().toString();
    }
}