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 <= str1.length, str2.length <= 1000
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;
}