> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/1092.-shortest-common-supersequence.md).

# 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.

{% hint style="info" %}
要找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。
{% endhint %}

```cpp
// 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;
}
```