# 1092 - Shortest Common Supersequence
解法一 - 暴力法
我們可以分成兩種情況:
str1 跟 str2 的當前 char 一樣:將兩邊的指針都往前,繼續搜尋最小的 supersequence
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];
}
};
Last updated