給出兩個(gè)字符串 str1 和 str2牺汤，返回同時(shí)以 str1 和 str2 作為子序列的最短字符串槐臀。如果答案不止一個(gè)爷速，則可以返回滿足條件的任意一個(gè)答案埃跷。

（如果從字符串 T 中刪除一些字符（也可能不刪除晌砾，并且選出的這些字符可以位于 T 中的 任意位置）壶冒，可以得到字符串 S巫糙，那么 S 就是 T 的子序列）

示例：

輸入：str1 = "abac", str2 = "cab"
輸出："cabac"
解釋：
str1 = "abac" 是 "cabac" 的一個(gè)子串港令，因?yàn)槲覀兛梢詣h去 "cabac" 的第一個(gè) "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一個(gè)子串秕磷，因?yàn)槲覀兛梢詣h去 "cabac" 末尾的 "ac" 得到 "cab"。
最終我們給出的答案是滿足上述屬性的最短字符串炼团。

提示：

1. 1 <= str1.length, str2.length <= 1000
2. str1 和 str2 都由小寫英文字母組成澎嚣。

思路：
Printing Shortest Common Supersequence

代碼：

class Solution {
public:
    string shortestCommonSupersequence(string X, string Y) {
        int m = X.length(); 
        int n = Y.length(); 

        // dp[i][j] contains length of shortest supersequence 
        // for X[0..i-1] and Y[0..j-1] 
        int dp[m + 1][n + 1]; 

        // Fill table in bottom up manner 
        for (int i = 0; i <= m; i++) 
        { 
            for (int j = 0; j <= n; j++) 
            { 
                // Below steps follow recurrence relation 
                if(i == 0) 
                    dp[i][j] = j; 
                else if(j == 0) 
                    dp[i][j] = i; 
                else if(X[i - 1] == Y[j - 1]) 
                    dp[i][j] = 1 + dp[i - 1][j - 1]; 
                else
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]); 
            } 
        } 

        // Following code is used to print shortest supersequence 

        // dp[m][n] stores the length of the shortest supersequence 
        // of X and Y 
        int index = dp[m][n]; 

        // string to store the shortest supersequence 
        string str; 

        // Start from the bottom right corner and one by one 
        // push characters in output string 
        int i = m, j = n; 
        while (i > 0 && j > 0) 
        { 
            // If current character in X and Y are same, then 
            // current character is part of shortest supersequence 
            if (X[i - 1] == Y[j - 1]) 
            { 
                // Put current character in result 
                str.push_back(X[i - 1]); 

                // reduce values of i, j and index 
                i--, j--, index--; 
            } 

            // If current character in X and Y are different 
            else if (dp[i - 1][j] > dp[i][j - 1]) 
            { 
                // Put current character of Y in result 
                str.push_back(Y[j - 1]); 

                // reduce values of j and index 
                j--, index--; 
            } 
            else
            { 
                // Put current character of X in result 
                str.push_back(X[i - 1]); 

                // reduce values of i and index 
                i--, index--; 
            } 
        } 

        // If Y reaches its end, put remaining characters 
        // of X in the result string 
        while (i > 0) 
        { 
            str.push_back(X[i - 1]); 
            i--, index--; 
        } 

        // If X reaches its end, put remaining characters 
        // of Y in the result string 
        while (j > 0) 
        { 
            str.push_back(Y[j - 1]); 
            j--, index--; 
        } 

        // reverse the string and return it 
        reverse(str.begin(), str.end()); 
        return str; 
    }
};