Stamping The Sequence Problem
Description
LeetCode Problem 936.
You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == ‘?’.
In one turn, you can place stamp over s and replace every letter in the s with the corresponding letter from stamp.
- For example, if stamp = “abc” and target = “abcba”, then s is “?????” initially. In one turn you can:
- place stamp at index 0 of s to obtain “abc??”,
- place stamp at index 1 of s to obtain “?abc?”, or
- place stamp at index 2 of s to obtain “??abc”.
Note that stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s).
We want to convert s to target using at most 10 * target.length turns.
Return an array of the index of the left-most letter being stamped at each turn. If we cannot obtain target from s within 10 * target.length turns, return an empty array.
Example 1:
1
2
3
4
5
6
Input: stamp = "abc", target = "ababc"
Output: [0,2]
Explanation: Initially s = "?????".
- Place stamp at index 0 to get "abc??".
- Place stamp at index 2 to get "ababc".
[1,0,2] would also be accepted as an answer, as well as some other answers.
Example 2:
1
2
3
4
5
6
Input: stamp = "abca", target = "aabcaca"
Output: [3,0,1]
Explanation: Initially s = "???????".
- Place stamp at index 3 to get "???abca".
- Place stamp at index 0 to get "abcabca".
- Place stamp at index 1 to get "aabcaca".
Constraints:
- 1 <= stamp.length <= target.length <= 1000
- stamp and target consist of lowercase English letters.
Sample C++ Code
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
class Solution {
public:
// Greedily match stamp with target with offset, ignoring already matched characters.
vector<int> movesToStamp(string stamp, string target) {
int NS = stamp.size(), NT = target.size();
vector<int> ans;
bool has_match;
do {
has_match = false;
for (int i = 0; i <= NT - NS; i++) {
bool ok = true;
int num_dot = 0;
for (int j = 0; j < NS; j++) {
if (target[i + j] == '.')
// take care we don't match only matched ones
num_dot++;
if (target[i + j] != '.' && stamp[j] != target[i + j]) {
// simple wildcard matching
ok = false;
break;
}
}
if (ok && num_dot < NS) {
has_match = true;
ans.push_back(i);
for (int j = 0; j < NS; j++)
target[i + j] = '.';
}
}
} while(has_match);
for (char a : target)
if (a != '.')
return {};
reverse(ans.begin(), ans.end());
return ans;
}
};