forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 1
/
stamping-the-sequence.cpp
64 lines (61 loc) · 1.94 KB
/
stamping-the-sequence.cpp
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Time: O((n - m) * m)
// Space: O((n - m) * m)
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
const int M = stamp.size(), N = target.size();
queue<int> q;
vector<bool> lookup(N);
vector<int> result;
vector<pair<unordered_set<int>, unordered_set<int>>> A;
for (int i = 0; i < N - M + 1; ++i) {
unordered_set<int> made, todo;
for (int j = 0; j < M; ++j) {
if (stamp[j] == target[i + j]) {
made.emplace(i + j);
} else {
todo.emplace(i + j);
}
}
A.emplace_back(made, todo);
if (!todo.empty()) {
continue;
}
result.emplace_back(i);
for (const auto& m : made) {
if (lookup[m]) {
continue;
}
q.emplace(m);
lookup[m] = true;
}
}
while (!q.empty()) {
auto i = q.front(); q.pop();
for (int j = max(0, i - M + 1); j < min(N - M, i) + 1; ++j) {
unordered_set<int>& made = A[j].first;
unordered_set<int>& todo = A[j].second;
if (!todo.count(i)) {
continue;
}
todo.erase(i);
if (!todo.empty()) {
continue;
}
result.emplace_back(j);
for (const auto& m : made) {
if (lookup[m]) {
continue;
}
q.emplace(m);
lookup[m] = true;
}
}
}
if (std::all_of(lookup.cbegin(), lookup.cend(), [](bool i){ return i; })) {
reverse(result.begin(), result.end());
return result;
}
return {};
}
};