给定两个字符串S和T,在一个长为T的空间,把S当章敲,即可以不断从空间内任何位置开始覆盖成S,问最后能否敲出T。正着DFS模拟敲章过程时间复杂度会非常高。反过来想,如果能敲成功,最后一次敲的一定是S,那就可以从T中搜索S所在位置把对应的所有字符打上*,意味着它们之前随意怎么敲都无所谓。再对剩下的可能的起始位置做类似的搜索,实际上只要满足除去*后和T有交集就可以作为倒数第二步,依次类推。最后得出来的就是反过来的敲章过程。这么得出的过程并不一定是最短的敲章过程。
/*
* @lc app=leetcode id=936 lang=cpp
*
* [936] Stamping The Sequence
*/
// @lc code=start
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
const int N = target.length(), M = stamp.length();
vector<int> res;
vector<bool> visited(N);
int total = 0;
const auto un_stamp = [&](int s) {
int l = M;
for (int i = 0; i < M; ++i) {
if (target[s + i] == '*') --l;
else if (target[s + i] != stamp[i]) return 0;
}
if (l != 0) fill(begin(target) + s, begin(target) + s + M, '*');
return l;
};
while (total < N) {
bool found = false;
for (int i = 0; i <= N - M; ++i) {
if (visited[i]) continue;
int l = un_stamp(i);
if (l == 0) continue;
visited[i] = true;
total += l;
res.push_back(i);
found = true;
}
if (!found) return {};
}
reverse(begin(res), end(res));
return res;
}
};
// @lc code=end