作者推荐
【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径
本文涉及知识点
状态压缩 字符串
LeetCode943 最短超级串
给定一个字符串数组 words，找到以 words 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中 任意一个 即可。
我们可以假设 words 中没有字符串是 words 中另一个字符串的子字符串。
示例 1：
输入：words = [“alex”,“loves”,“leetcode”]
输出：“alexlovesleetcode”
解释：“alex”，“loves”，“leetcode” 的所有排列都会被接受。
示例 2：
输入：words = [“catg”,“ctaagt”,“gcta”,“ttca”,“atgcatc”]
输出：“gctaagttcatgcatc”
参数范围：
1 <= words.length <= 12
1 <= words[i].length <= 20
words[i] 由小写英文字母组成
words 中的所有字符串 互不相同
动态规划
假定结果串是s。则s的某个后缀一定是words[x]。← \leftarrow← 否则，删除最后一个字符，更短。我们可以枚举其后缀。
inx[i]和inx[j]是words[i] words[j] 在s 中第一次出现的下标。
{ w o r d s 中没有字符串是 w o r d s 中另一个字符串的子字符串 w o r d s 中的所有字符串互不相同 → \begin{cases} words 中没有字符串是 words 中另一个字符串的子字符串 \\ words 中的所有字符串 互不相同 \\ \end{cases} \rightarrow{words中没有字符串是words中另一个字符串的子字符串words中的所有字符串互不相同→
{ i n x [ i ] ≠ i n x [ j ] i n x [ i ] < i n x [ j ] → i n x [ i ] + w o r d s [ i ] . l e n g h t < i n x [ j ] + w o r d s [ j ] . l e n g t h → 否则 w o r d s [ i ] 包括 w r o d s [ j ] \begin{cases} inx[i]\neq inx[j] \\ inx[i]<inx[j] \rightarrow inx[i]+words[i].lenght < inx[j]+words[j].length \rightarrow 否则words[i]包括wrods[j] \\ \end{cases}{inx[i]=inx[j]inx[i]<inx[j]→inx[i]+words[i].lenght<inx[j]+words[j].length→否则words[i]包括wrods[j]
→ \rightarrow→ 只需要考虑两个字符串的重叠，不需要考虑更多。
动态规格的状态
那些字符串已经处理，最后字符串。preMask 记录前一个状态有那些字符已经处理。preEnd记录最后一个字符。d[i][mask]记录符合要求的最短串，如果有多个最短串，取任意一个，其后缀一定是words[i]。
动态规划的转移方程
oldEnd mask，枚举新的结束字符串。newEnd。如果mask已经包括1 << newEnd，忽略。
const string newS = dp[oldEnd][mask] + Right(words[newEnd], vNeedAdd[oldEnd][newEnd]);
如果dp[newEnd][iNewMask]为空或比newS 短，更新。
动态规划的初始状态
除只有一个字符串的状态外，全部为空。
动态规划的填表顺序
处理了新串时，mask一定变大。mask从小到大，一定可以保证无后效性。
动态规划的返回值
最短串 i = 0 m c − 1 最短串\Large_{i=0}^{m_c-1}最短串i=0mc−1(dp[i].back())
代码
核心代码
class Solution { public: string shortestSuperstring(vector<string>& words) { m_c = words.size(); m_iMaskCount = 1 << m_c; vector<vector<int>> vNeedAdd(m_c, vector<int>(m_c)); for (int i = 0; i < m_c; i++) { for (int j = 0; j < m_c; j++) { vNeedAdd[i][j] = NeedAdd(words[i], words[j]); } } vector<vector<string>> dp(m_c,vector<string>(m_iMaskCount)); for (int i = 0; i < m_c; i++) { dp[i][1 << i] = words[i]; } for (int mask = 0; mask < m_iMaskCount; mask++) { for (int oldEnd = 0; oldEnd < m_c; oldEnd++) { if (dp[oldEnd][mask].empty()) { continue;//非法状态 } for (int newEnd = 0; newEnd < m_c; newEnd++) { const int iNewMask = (1 << newEnd) | mask; if (iNewMask == mask) { continue;//此字符串已经处理 } const string newS = dp[oldEnd][mask] + Right(words[newEnd], vNeedAdd[oldEnd][newEnd]); if (dp[newEnd][iNewMask].empty() ||(newS.length() < dp[newEnd][iNewMask].length())) { dp[newEnd][iNewMask] = newS; } } } } string strRet = dp[0].back(); for (int i = 0; i < dp.size(); i++) { if (dp[i].back().length() < strRet.length()) { strRet = dp[i].back(); } } return strRet; } string Right(const string& s, int r) { return s.substr(s.length() - r); } int NeedAdd(const string& s1, const string& s2) { int iSameLen = min(s1.length(),s2.length()); for (; iSameLen > 0; iSameLen--) { if (s1.substr(s1.length() - iSameLen) == s2.substr(0, iSameLen)) { break; } } return s2.length() - iSameLen; } int m_c,m_iMaskCount; };
测试用例
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() { vector<string> words; { Solution sln; words = { "alex", "loves", "leetcode" }; auto res = sln.shortestSuperstring(words); Assert(res.length(), string("alexlovesleetcode").length()); } { Solution sln; words = { "alex", "loves", "leetcode" }; auto res = sln.shortestSuperstring(words); Assert(res.length(), string("alexlovesleetcode").length()); } { Solution sln; words = { "catg","ctaagt","gcta","ttca","atgcatc" }; auto res = sln.shortestSuperstring(words); Assert(res.length(), string("gctaagttcatgcatc").length()); } }
2023年1月版
class Solution {
public:
string shortestSuperstring(vector& words) {
m_c = words.size();
m_iMaskNum = 1 << m_c;
m_vMaskEndIndex.assign(m_iMaskNum, vector(m_c, INT_MAX));
m_vMaskEndIndexStr.assign(m_iMaskNum, vector(m_c, “”));
{
for (int k = 0; k < m_c; k++)
{
m_vMaskEndIndex[0][k] = 0;
}
}
m_vBeginEndLen.assign(m_c, vector(m_c));
Init(words);
for (int iMask = 0; iMask < m_iMaskNum; iMask++)
{
for (int endIndex = 0; endIndex < m_c; endIndex++)
{
for (int iNewIndex = 0; iNewIndex < m_c; iNewIndex++)
{
if ((1 << iNewIndex) & iMask)
{
//新旧串重复，包括相同的字符串
continue;
}
if (0 == iMask)
{
m_vMaskEndIndex[1 << iNewIndex][iNewIndex] = words[iNewIndex].length();
m_vMaskEndIndexStr[1 << iNewIndex][iNewIndex] = words[iNewIndex];
continue;
}
if (!((1 << endIndex) & iMask))
{
continue;
}
const int iAddLen = m_vBeginEndLen[endIndex][iNewIndex];
const int iNewLen = m_vMaskEndIndex[iMask][endIndex] + iAddLen;
int& iOldLen = m_vMaskEndIndex[(1 << iNewIndex) | iMask][iNewIndex];
if (iNewLen < iOldLen)
{
iOldLen = iNewLen;
m_vMaskEndIndexStr[(1 << iNewIndex) | iMask][iNewIndex] = m_vMaskEndIndexStr[iMask][endIndex] + words[iNewIndex].substr(words[iNewIndex].length()- iAddLen,iAddLen);
}
}
}
}
int iMin = m_vMaskEndIndex[m_iMaskNum - 1][0];
string strRet = m_vMaskEndIndexStr[m_iMaskNum - 1][0];
for (int i = 1; i < m_c; i++)
{
const int& iLen = m_vMaskEndIndex[m_iMaskNum - 1][i];
if (iLen < iMin)
{
iMin = iLen;
strRet = m_vMaskEndIndexStr[m_iMaskNum - 1][i];
}
}
return strRet;
}
void Init(const vector& words)
{
for (int i = 0; i < words.size(); i++)
{
for (int j = 0; j < words.size(); j++)
{
for (int iAdd = 0; iAdd <= words[j].length(); iAdd++)
{
const int iSameLen = words[j].length() - iAdd;
int iPos = words[i].length() - iSameLen;
if (iPos < 0)
{
continue;
}
if (words[i].substr(iPos, iSameLen) == words[j].substr(0, iSameLen))
{
m_vBeginEndLen[i][j] = iAdd;
break;
}
}
}
}
}
vector<vector> m_vMaskEndIndex;
vector<vector> m_vMaskEndIndexStr;
vector<vector> m_vBeginEndLen;
int m_c;
int m_iMaskNum;
};
