1092. Shortest Common Supersequence

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.)

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Note:

1. 1 <= str1.length, str2.length <= 1000

2. str1 and str2 consist of lowercase English letters.

要找shortest common supersequence有點類似一個最小公倍數的概念，可以先找到longest common subsequence之後再把各個字串上缺少的字符加到結果中。 先紀錄一個2-D DP table存下找longest common subsequence的所有中間過程。 dp state transition: dp[i][j] = dp[i - 1][j - 1] + 1 if str1[i - 1] == str2[j - 1] dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) if str1[i - 1] != str2[j - 1] 每一個dp table中的grid都可以由上方、左邊、左上的grid得到，有這個關係就能得知要加哪一個字串中的字符到結果裡。但這個結果必須倒著回來，因為如果是正的方向沒辦法得到這項的關係幫忙決定要加什麼字符。 因為加的順序是倒過來的，所以最後結果要reverse。

// Dynamic Programming + LCS Calculation
string shortestCommonSupersequence(string str1, string str2) { // time: O(m * n); space: O(m * n)
    int m = str1.length(), n = str2.length();
    vector<vector<int> > dp(m + 1, vector<int> (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]);
            }
        }
    }
    string res;
    int i = m - 1, j = n - 1;
    while (i >= 0 || j >= 0) {
        if ((i < 0) ^ (j < 0)) {
            res += (i < 0) ? str2[j--] : str1[i--];
        } else if(str1[i] == str2[j]) {
            res += str1[i];
            i--, j--;              
        } else {
            res += dp[i + 1][j] > dp[i][j + 1] ? str2[j--] : str1[i--];
        }
    }
    reverse(res.begin(), res.end());
    return res;
}