题目
你想要用小写字母组成一个目标字符串 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<int> vRet; std::unordered_set<int> 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<int>(vRet.rbegin(), vRet.rend()); } return {}; } vector<int> m_vCanOver;//target[i,i+m)和印章不同且非*字符，为0则可以盖章 vector<vector<int>> m_vNotSame;//m_vNotSameStar[i]的元素j0,j1等。由于i处的字符不同，所以无法在j0,j1处盖章
}; ##. 测试用例 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版
