# 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;
}
};
``````

## 解法二 - Memoization

``````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];
}
};
``````

## 解法三 - DP

``````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];
}
};
``````