【动态规划】【字符串】【状态压缩】943 最短超级串

作者推荐

【动态规划】【广度优先搜索】【状态压缩】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 中第一次出现的下标。
$$\{\begin{array}{l}words中没有字符串是words中另一个字符串的子字符串\\ words中的所有字符串互不相同\end{array}\to$$
$$\{\begin{array}{l}inx[i]\ne inx[j]\\ inx[i]<inx[j]\to inx[i]+words[i].lenght<inx[j]+words[j].length\to 否则words[i]包括wrods[j]\end{array}$$
$\to$ 只需要考虑两个字符串的重叠，不需要考虑更多。

动态规格的状态

那些字符串已经处理，最后字符串。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}$(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;
};

扩展阅读

视频课程

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

如何你想快

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

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 **C+

+17**
如无特殊说明，本算法用**C++**实现。