# 1092 - Shortest Common Supersequence

解法一 - 暴力法

我們可以分成兩種情況：

1. str1 跟 str2 的當前 char 一樣：將兩邊的指針都往前，繼續搜尋最小的 supersequence

2. str1 跟 str2 的當前 char 不一樣：將兩邊的指針分別往前，搜尋兩種可能下，最小的 supersequence

實作如下：

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        return findAns(str1, str2, 0, 0, "");
    }

private:
    string findAns(string& s1, string& s2, int s1_ptr, int s2_ptr, string tmp) {
        if(s1_ptr == s1.length() && s2_ptr == s2.length())
            return tmp;

        if(s1_ptr == s1.length())
            return tmp + s2.substr(s2_ptr, s2.length()-s2_ptr);

        if(s2_ptr == s2.length())
            return tmp + s1.substr(s1_ptr, s1.length()-s1_ptr);

        // If two chars match, then include char and keep searching
        if(s1[s1_ptr] == s2[s2_ptr]) {
            string t = tmp; 
            t += s1[s1_ptr];
            return findAns(s1, s2, s1_ptr+1, s2_ptr+1, t);
        }

        // If two chars don't match, then include each char and keep searching
        string c1, c2;
        string t = tmp;
        t += s1[s1_ptr];
        c1 = findAns(s1, s2, s1_ptr+1, s2_ptr, t);

        t.pop_back();
        t += s2[s2_ptr];
        c2 = findAns(s1, s2, s1_ptr, s2_ptr+1, t);

        return c1.length() < c2.length() ? c1 : c2;
    }
};

跑起來會 Memory Limit Exceeded。

解法二 - Memoization

有一點要特別注意，有時候可能會發生 s1_ptr 跟 s2_ptr 之前已經算過，但因為當前的 tmp 不同，所以會讓要儲存的值發生變化。所以我們用 s1_ptr|s2_ptr|tmp 當做 key，用一個 hash table 來存。

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        unordered_map<string, string> dp;
        return findAns(str1, str2, 0, 0, "", dp);
    }

private:
    string findAns(string& s1, string& s2, int s1_ptr, int s2_ptr, string tmp, unordered_map<string, string>& dp) {
        if(s1_ptr == s1.length() && s2_ptr == s2.length())
            return tmp;

        if(s1_ptr == s1.length())
            return tmp + s2.substr(s2_ptr, s2.length()-s2_ptr);

        if(s2_ptr == s2.length())
            return tmp + s1.substr(s1_ptr, s1.length()-s1_ptr);

        // If two chars match, then include char and keep searching
        string key = to_string(s1_ptr) + "|" + to_string(s2_ptr) + "|" + tmp;
        if(dp.find(key) == dp.end()) {
            if(s1[s1_ptr] == s2[s2_ptr]) {
                tmp += s1[s1_ptr];
                dp[key] = findAns(s1, s2, s1_ptr+1, s2_ptr+1, tmp, dp);
            }
            else {
                // If two chars don't match, then include each char and keep searching
                tmp += s1[s1_ptr];
                string c1 = findAns(s1, s2, s1_ptr+1, s2_ptr, tmp, dp);

                tmp.pop_back();
                tmp += s2[s2_ptr];
                string c2 = findAns(s1, s2, s1_ptr, s2_ptr+1, tmp, dp);

                dp[key] = c1.length() < c2.length() ? c1 : c2;
            }
        }

        return dp[key];
    }
};

可惜這個解法還是會 MLE。

解法三 - DP

我們其實可以先算出這兩個字串的 LCS，然後接下來只要分別把不在 LCS 裡面的字母都加上去就好，實作如下：

class Solution {
public:
    string shortestCommonSupersequence(string& A, string& B) {
        int i = 0, j = 0;
        string res = "";
        for (char c : lcs(A, B)) {
            while (A[i] != c)
                res += A[i++];
            while (B[j] != c)
                res += B[j++];
            res += c, i++, j++;
        }
        return res + A.substr(i) + B.substr(j);
    }

    string lcs(string& A, string& B) {
        int n = A.size(), m = B.size();
        vector<vector<string>> dp(n + 1, vector<string>(m + 1, ""));

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (A[i] == B[j])
                    dp[i + 1][j + 1] = dp[i][j] + A[i];
                else
                    dp[i + 1][j + 1] = dp[i + 1][j].size() > dp[i][j + 1].size() ?  dp[i + 1][j] : dp[i][j + 1];
            }
        }

        return dp[n][m];
    }
};