【动态规划】【字符串】1092. 最短公共超序列

作者推荐

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

本文涉及知识点

动态规划汇总

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的含义如下：
$\begin{cases} 此超串的末尾已经匹配了str1,str2 & 3 \\ 此超串末尾匹配了str1 & 1 \\ 此超串末尾匹配了str2 & 2 \end{cases}$

动态规划的转移方程

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);
$\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][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;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛