C++算法：利用拓扑排序解决戳印序列

LeetCode936题目

你想要用小写字母组成一个目标字符串 target。
开始的时候，序列由 target.length 个 ‘?’ 记号组成。而你有一个小写字母印章 stamp。
在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行 10 * target.length 个回合。
举个例子，如果初始序列为 “???”，而你的印章 stamp 是 “abc”，那么在第一回合，你可以得到 “abc??”、“?abc?”、“??abc”。（请注意，印章必须完全包含在序列的边界内才能盖下去。）
如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。
例如，如果序列是 “ababc”，印章是 “abc”，那么我们就可以返回与操作 “???” -> “abc??” -> “ababc” 相对应的答案 [0, 2]；
另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成。任何超过此数字的答案将不被接受。
1 <= stamp.length <= target.length <= 1000
stamp 和 target 只包含小写字母。

分析

设target的长度为n,设印章的长度为m。印章的最左端对齐target[i]处盖章，我们简称为盖在i处。同一处只需要覆盖一次，因为同处盖章会完全覆盖前一次盖章。假定两次盖章，先后盖在i1,i2处。

正着想太复杂，倒着想。将target盖章后，变成???，盖章的位置必须和印章相同或是号。有多处可以盖，任选一处。因为盖章只会将字符变成，不会将*变成其它字符。任意顺序盖，不会将之前能盖的变成不能盖，顶多增加盖章次数。由于任意位置都只会盖一次，所以最多盖n-m+1次，不会超过回合数。

用例分析

设target的长度为n,设印章的长度为m。印章的最左端对齐target[i]处盖章，我们简称为盖在i处。同一处只需要覆盖一次，因为同处盖章会完全覆盖前一次盖章。

错误猜想

这题太难了，想了好几个思路，发现都是错的。

错误猜想：target[i,i+m)等于印章，则前面的印章可以按顺序盖。

一，如果target[i,i+m)等于印章,假定结果系列包括x和i，且x小于i。如果先盖i,再盖x，可以调整为先盖x,再盖i。前者需要确保[x, x+m)能改成，后者值需要确保[x,i)。如果盖在x处和i处，有重叠部分则，x+m >i。前者能盖成，则后者一定能盖成。
二，i0是x的最大值，i1是x的次大值。根据规律二，只需要考虑两种可能{i1,i0,i}或{i0,i1,x}。aaabc abccabc。猜想一正确，但无价值。
###　不能直接调整顺序
直觉上，我们可以从左向右盖。印章必须完全包含在序列的边界，所以i为0和i为n-m处必定会盖章。如果[0,m)处没有盖章，则将0处盖章移到整个操作系列的最前面。假定有x取[0,m),且先在x处盖章，再在0处盖章。那么[0,m)处和印章相同,[m,x+n)和印章有x个字符相同。如果先0处，再x处，则[0,x)处和印章前x个字符相同，[x,x+n)和印章完全相同。不能直接调整顺序。如：abcc。

分情况讨论

Rec(i1)返回target[i1,n)是否能用印章完全覆盖，以下三个条件之一成立，则Rec(i1)能用印章完全覆盖。
一，target[i1,i1+m)等于印章,且Rec(i1+n)能覆盖成。
二，target[i1,i1+x)是印章的前缀，target[i1+x,i1+x+m)等于印章，Rec(i1+x+m)能覆盖。先盖i1处，再盖i1+x处。
三，target[i1,i1+m)等于印章，target[i1+m,i1+m+x)是印章的后缀，Rec(i1+m+x)能覆盖。
先盖在i1+x处，再盖再i处。
由于i1是最左端，所以必须盖再i1处。[i1+m)可能部分区域可能被重新覆盖。则情况可以简化为：
第二条是错误的，比如：目标串为aaabc，印章为abc。aab并不等于印章。target[i1,i1+x)是印章的前缀，Rev(i1+x)能被覆盖。
第三条也是错误。abababc,abc???->ababc??->abababc。

核心代码

class Solution {
public:
vector movesToStamp(string stamp, string target) {
const int n = target.length();
const int m = stamp.length();
m_vCanOver.assign(n - m + 1, stamp.size());
std::queue que;
m_vNotSame.resize(target.size());
for (int i = 0; i < m_vCanOver.size(); i++)
{
for (int j = 0; j < m; j++)
{
if (target[i + j] == stamp[j])
{
m_vCanOver[i]–;
}
else
{
m_vNotSame[i + j].emplace_back(i);
}
}
if (0 == m_vCanOver[i])
{
que.emplace(i);
}
}

	vector vRet;
	std::unordered_set hasDo;
	while (que.size()&&(hasDo.size() < n ) )
	{
		const auto cur = que.front();
		que.pop();
		vRet.emplace_back(cur);
		for (int i = cur; i < cur + m; i++)
		{
			for (const auto& j : m_vNotSame[i])
			{
				m_vCanOver[j]--;
				if (0 == m_vCanOver[j])
				{
					que.emplace(j);
				}
			}
			m_vNotSame[i].clear();
			hasDo.emplace(i);
		}
	}

	if (hasDo.size() == n )
	{
		return vector(vRet.rbegin(), vRet.rend());
	}
	return {};
}
vector m_vCanOver;//target[i,i+m)和印章不同且非*字符，为0则可以盖章
vector> m_vNotSame;//m_vNotSameStar[i]的元素j0,j1等。由于i处的字符不同，所以无法在j0,j1处盖章
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

};
##. 测试用例
struct CDebugParam
{
string targe;
string stamp;
vector result;
};
int main()
{
vector< CDebugParam> params = { {“aabc”,“abc”,{0,1}}, {“abc”,“abc”,{0}},{“abcc”,“abc”,{1,0}} };
for (const auto& par : params)
{
auto res = Solution().movesToStamp(par.stamp, par.targe);
assert(res.size() == par.result.size());
for (int i = 0; i < res.size(); i++)
{
assert(res[i] == par.result[i]);
}
}

//CConsole::Out(res);
}

其它

视频课程

要是你认为本篇难道较大，不好入手，推荐你先学习基础算法的课程，我已完成部分，余下部分持续更新中，就在CSDN学院。
https://edu.csdn.net/course/detail/38771

C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

相关下载

如果你想观其大略，建设下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653