题目
你想要用小写字母组成一个目标字符串 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 只包含小写字母。
分析
自己想出来的笨办法，时间复杂度较低。公认的方法是拓扑排序。
代码
class Solution { public: vector<int> movesToStamp(string stamp, string target) { int iWindowCount = target.length() - stamp.length() + 1; m_strDebug = target; unordered_map<int, unordered_set<int>> vNotSame; std::unordered_multiset<int> setNeed; for (int i = 0; i < target.size(); i++) { setNeed.emplace(i); } vector<vector<int>> vDirect(target.length()); std::vector<int> vQue; for (int i = 0; i < iWindowCount; i++) { for (int j = 0; j < stamp.size(); j++) { if (stamp[j] != target[i + j]) { vNotSame[i].emplace(i + j); vDirect[i + j].emplace_back(i); } } if (!vNotSame.count(i)) { vQue.emplace_back(i); } } int index = 0; while (setNeed.size() && (index < vQue.size())) { const auto cur = vQue[index]; index++; for (int i = 0; i < stamp.length(); i++) { setNeed.erase(i + cur); assert(('?' == m_strDebug[i + cur]) || (m_strDebug[i + cur] == stamp[i])); m_strDebug[i + cur] = '?'; for (const auto& n : vDirect[i + cur]) { if (!vNotSame.count(n)) { continue; } vNotSame[n].erase(i + cur); if (0 == vNotSame[n].size()) { vQue.emplace_back(n); vNotSame.erase(n); } } } // CConsole::Out(m_strDebug); } vector<int> vRet(vQue.begin(), vQue.begin() + index); return setNeed.size() ? vector<int>{} : vector<int>(vRet.rbegin(), vRet.rend()); } string m_strDebug; };
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17
相关下载
doc版文档，排版好
https://download.csdn.net/download/he_zhidan/88348653
