Sponsored
Sponsored
This approach involves reversing the stamping process. Instead of trying to form the target from '?' gradually, we attempt to convert the target into '?' by 'un-stamping' in a greedy way.
We can try and 'stamp out' the pattern from the target where it matches. This continues until we've stamped out the entire target or until we determine it's impossible to do so within the given constraints.
Time Complexity: O((N-M+1)*M) where N is the length of target and M is the length of stamp. We effectively iterate through the length of the target and for each possible stamping position, we may iterate through the stamp.
Space Complexity: O(N) to hold the result of the stampping sequence.
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 vector<int> movesToStamp(string stamp, string target) {
8 int m = stamp.size(), n = target.size();
9 vector<int> res;
10 vector<bool> visited(n, false);
11 int stars = 0;
12
13 while (stars < n) {
14 bool stamped = false;
15 for (int i = 0; i <= n - m; ++i) {
16 if (!visited[i] && canStamp(target, stamp, i)) {
17 stars += replaceWithStar(target, i, m);
18 stamped = true;
19 visited[i] = true;
20 res.push_back(i);
21 if (stars == n) break;
22 }
23 }
24 if (!stamped) return {};
25 }
26
27 reverse(res.begin(), res.end());
28 return res;
29 }
30
31 bool canStamp(string &target, string &stamp, int pos) {
32 for (int i = 0; i < stamp.size(); ++i) {
33 if (target[i + pos] != '?' && target[i + pos] != stamp[i]) return false;
34 }
35 return true;
36 }
37
38 int replaceWithStar(string &target, int pos, int len) {
39 int count = 0;
40 for (int i = 0; i < len; ++i) {
41 if (target[i + pos] != '?') {
42 target[i + pos] = '?';
43 count++;
44 }
45 }
46 return count;
47 }
48};
49
50// Example usage
51int main() {
52 Solution sol;
53 vector<int> result = sol.movesToStamp("abc", "ababc");
54 for (int index : result) {
55 printf("%d ", index);
56 }
57 printf("\n");
58 return 0;
59}The C++ solution is similar to the C solution but leverages object-oriented features. We maintain a vector of indices representing possible stamping positions and check if 'stamp' can cover the current part of the 'target'.
If it can, we replace the corresponding part with '?' and record the index. We repeat this process until the target is fully stamped into '?'. The result vector is reversed to reflect the order of stamping turns.