作者推荐
本文涉及知识点
LeetCode1092最短公共超序列
给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。
如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。
示例 1：
输入：str1 = “abac”, str2 = “cab”
输出：“cabac”
解释：
str1 = “abac” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 的第一个 "c"得到 “abac”。
str2 = “cab” 是 “cabac” 的一个子串，因为我们可以删去 “cabac” 末尾的 “ac” 得到 “cab”。
最终我们给出的答案是满足上述属性的最短字符串。
示例 2：
输入：str1 = “aaaaaaaa”, str2 = “aaaaaaaa”
输出：“aaaaaaaa”
提示：
1 <= str1.length, str2.length <= 1000
str1 和 str2 都由小写英文字母组成。
动态规划
原理
超串一定以str1.back或str2.back结尾 。
动态规划的状态表示
dp[i][j][use]=x，表示str1[0,i)和str2[0,j)的最短超串长度。use的含义如下：
{ 此超串的末尾已经匹配了 s t r 1 , s t r 2 3 此超串末尾匹配了 s t r 1 1 此超串末尾匹配了 s t r 2 2 \begin{cases} 此超串的末尾已经匹配了str1,str2 & 3 \\ 此超串末尾匹配了str1 & 1 \\ 此超串末尾匹配了str2 & 2 \end{cases}⎩⎨⎧此超串的末尾已经匹配了str1,str2此超串末尾匹配了str1此超串末尾匹配了str2312
动态规划的转移方程
dp[i][j][use] 更新dp[i+1][j][use1] preCh = (1&use) ? str1[i-1] : str2[j-1]。const int use1 = bNew ? 1 : (1 | use);
{ d p [ i + 1 ] [ j ] [ u s e 1 ] = m i n ( , d p [ i ] [ j ] [ u s e ] + 1 ) ( p r e C h ! = s t r 1 [ i ] ) 或 ( 1 位与 u s e ) d p [ i + 1 ] [ j ] [ u s e 1 ] = m i n ( , d p [ i ] [ j ] [ u s e ] ) e l s e \begin{cases} dp[i+1][j][use1] = min(,dp[i][j][use]+1) & (preCh!=str1[i])或(1位与use) \\ dp[i+1][j][use1] = min(,dp[i][j][use]) & else \\ \end{cases}{dp[i+1][j][use1]=min(,dp[i][j][use]+1)dp[i+1][j][use1]=min(,dp[i][j][use])(preCh!=str1[i])或(1位与use)else
更新dp[i][j+1] [use1]类似
动态规划的填表顺序
I+j之和从1到大处理，use 从1到3，这样可以保证动态规划的无后效性。
动态规划的初始值
dp[1][0][1] =1;
dp[0][1][2] = 1;
其它dp 的值INT_MAX/2
动态规划的返回值
根据dp2 逆序组装。
代码
核心代码
class Solution { public: string shortestCommonSupersequence(string str1, string str2) { m_r = str1.length(); m_c = str2.length(); vector<vector<vector<int>>> dp(m_r + 1, vector<vector<int>>(m_c + 1,vector<int>(4, INT_MAX / 2))); dp[1][0][1] =1; dp[0][1][2] = 1; for (int len = 1; len < m_r + m_c; len++) { for (int len1 = max(0,len-m_c); len1 <= min(len, m_r); len1++) { const int len2 = len - len1; for (int use = 1; use <= 3; use++) { const int preLen = dp[len1][len2][use]; if (preLen >= INT_MAX / 2) { continue; } const char preCh = (1 & use) ? str1[len1 - 1] : str2[len2 - 1]; if (len1 < m_r) { bool bNew = (preCh != str1[len1]) || (1 & use ); const int use1 = bNew ? 1 : (1 | use); const int iNewLen = preLen + bNew; dp[len1 + 1][len2][use1] = min(dp[len1 + 1][len2][use1], iNewLen); } if (len2 < m_c) { bool bNew = (preCh != str2[len2]) || (2 & use ); const int use1 = bNew ? 2 : (2 | use); const int iNewLen = preLen + bNew; dp[len1 ][len2 + 1][use1] = min(dp[len1][len2 + 1][use1], iNewLen); } } } } string strRet; for (int len1 = m_r, len2 = m_c; len1 + len2 > 0; ) { int use = std::min_element(dp[len1][len2].begin(), dp[len1][len2].end()) - dp[len1][len2].begin(); const char preCh = (1 & use) ? str1[len1 - 1] : str2[len2 - 1]; strRet += preCh; if (1 & use ) { len1--; } if (2 & use ) { len2--; } } std::reverse(strRet.begin(), strRet.end()); return strRet; } int m_r, m_c; };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string str1,str2; { Solution sln; str1 = "abac", str2 = "cab"; auto res = sln.shortestCommonSupersequence(str1, str2); assert(-1 != res.find(str1)); assert(-2 != res.find(str1)); Assert((int)res.length(),5 ); } { Solution sln; str1 = "aaaaaaaa", str2 = "aaaaaaaa"; auto res = sln.shortestCommonSupersequence(str1, str2); assert(-1 != res.find(str1)); assert(-2 != res.find(str1)); Assert(res.length(), string("aaaaaaaa").length()); } }
2023年1月版
先求最长公共子序列。
如果str1[i]==str2[j]， 则一个字符匹配两个串。
否则比较dp[i-1][j] 和dp[i][j-1]，采用公共子序列大的。
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
vector<vector> dp;
{
dp.assign(str1.length() + 1, vector(str2.length() + 1));
for (int i = 1; i <= str1.length(); i++)
{
for (int j = 1; j <= str2.length(); j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (str1[i-1] == str2[j-1])
{
dp[i][j] = max(dp[i][j],dp[i - 1][j - 1] + 1);
}
}
}
}
string str;
int i = str1.length();
int j = str2.length();
str1 = " " + str1;
str2 = " " + str2;
while (i > 0 || j > 0)
{
if (0 == i)
{
str += str2[j–];
}
else if (0 == j)
{
str += str1[i–];
}
else if (str1[i] == str2[j])
{
str += str1[i];
i–, j–;
}
else
{
if (dp[i - 1][j] == dp[i][j])
{
str += str1[i–];
}
else
{
str += str2[j–];
}
}
}
return std::string(str.rbegin(), str.rend());
}
};
2023年8月版
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
m_c1 = str1.length();
m_c2 = str2.length();
vector<vector> dp(m_c1, vector(m_c2));
vector < vector<pair<int, int>>> vPre(m_c1, vector<pair<int, int>>(m_c2,std::make_pair<>(-1,-1)));
dp[0][0] = str1[0] == str2[0];
if (0 == dp[0][0])
{
vPre[0][0] = std::make_pair(0, -1);
}
for (int j = 1; j < m_c2; j++)
{
if (str1[0] == str2[j])
{
dp[0][j] = 1;
vPre[0][j] = std::make_pair(-1, j - 1);
}
else
{
dp[0][j] = dp[0][j - 1];
vPre[0][j] = std::make_pair(0, j - 1);
}
}
for (int i = 1; i < m_c1; i++)
{
if (str1[i] == str2[0])
{
dp[i][0] = 1;
vPre[i][0] = std::make_pair(i - 1, -1);
}
else
{
dp[i][0] = dp[i-1][0];
vPre[i][0] = std::make_pair(i-1,0);
}
}
for (int i = 1; i < m_c1; i++)
{
for (int j = 1; j < m_c2; j++)
{
if (str1[i] == str2[j])
{
dp[i][j] = 1 + dp[i - 1][j - 1];
vPre[i][j] = std::make_pair(i - 1, j - 1);
continue;
}
if (dp[i - 1][j] > dp[i][j - 1])
{
dp[i][j] = dp[i - 1][j];
vPre[i][j] = std::make_pair(i - 1, j);
}
else
{
dp[i][j] = dp[i ][j - 1];
vPre[i][j] = std::make_pair(i , j - 1);
}
}
}
int iNum = dp.back().back();
vector vRet;
auto it = std::make_pair(m_c1-1,m_c2-1);
for ( 😭-1 != it.first) && (-1 != it.second)😉
{
auto pre = vPre[it.first][it.second];
if (it.first != pre.first)
{
vRet.emplace_back(str1[it.first]);
}
else
{
vRet.emplace_back(str2[it.second]);
}
it = pre;
}
for (int i = it.first; i >= 0; i–)
{
vRet.emplace_back(str1[i]);
}
for (int i = it.second; i >= 0; i–)
{
vRet.emplace_back(str2[i]);
}
std::reverse(vRet.begin(), vRet.end());
vRet.emplace_back(0);
return vRet.data();
}
int m_c1, m_c2;
};
