戳印序列原理及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变成???，某个字符系列除已经变成???问号的部分，其它部分和印章全部相同。

代码

class Solution {
public:
vector movesToStamp(string stamp, string target) {
int m = stamp.size();
int n = target.size();
//vCanLast[i]为x表示。target[i]到target[i+m-1] 共有x个字符和stamp不同。完全相同，为0表示，在i除及后续盖章，
//可以保证target[i]到target[i+m-1] 可以达成目标
//利用拓扑排序解决
m_iWindowNum = n - m + 1;
vector vNeedModify(m_iWindowNum, m);
vector vDirect(n);
std::stack sta;
for (int i = 0; i < m_iWindowNum; i++)
{
for (int j = 0; j < m; j++)
{
if (target[i + j] == stamp[j])
{
vNeedModify[i]–;
if (0 == vNeedModify[i])
{
sta.push(i);
}
}
else
{
vDirect[i + j].push_back(i);
}
}
}

	 vector vHasModify(n);
	 vector ret;
	 while (sta.size())
	 {
		 int iCur = sta.top();
		 sta.pop();
		 ret.push_back(iCur);
		 for (int j = 0; j < m; j++)
		 {
			 if (vHasModify[iCur + j])
			 {
				 continue;
			 }
			 vHasModify[iCur + j] = 1;
			 for (auto& dd : vDirect[iCur + j])
			 {
				 vNeedModify[dd]--;
				 if (0 == vNeedModify[dd])
				 {
					 sta.push(dd);
				 }
			 }
		 }
	 }

	 if (n == std::accumulate(vHasModify.begin(), vHasModify.end(), 0))
	 {
		 return vector(ret.rbegin(), ret.rend());
	 }
	 return vector();
 }
 int m_iWindowNum;//滑动窗口数量
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
31
32

};

其它

视频课程

如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
[https://edu.csdn.net/lecturer/6176]

(https://edu.csdn.net/lecturer/6176)

测试环境

win7 VS2019 C++17

相关下载

doc版文档，排版好
https://download.csdn.net/download/he_zhidan/88348653