0936 - Stamping The Sequence (Hard)
Problem Link
https://leetcode.com/problems/stamping-the-sequence
Problem Statement
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"andtarget = "abcba", thensis"?????"initially. In one turn you can:- place
stampat index0ofsto obtain"abc??", - place
stampat index1ofsto obtain"?abc?", or - place
stampat index2ofsto obtain"??abc".
Note that
stampmust be fully contained in the boundaries ofsin order to stamp (i.e., you cannot placestampat index3ofs). - place
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:
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:
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 <= 1000stampandtargetconsist of lowercase English letters.
Approach 1: Greedy
We first try the first stamp and mark those characters to. Then build some new stamps to check if they exist in target, if so mark them and repeat the process until all characters are stamped.
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
int n = stamp.size(), total = 0, k = -1;
vector<int> ans;
// "abca"
// "aabcaca"
while (k) {
k = 0;
for (int j = n; j > 0; j--) {
for (int i = 0; i <= n - j; i++) {
// build the new stamp
string new_stamp = string(i, '*') + stamp.substr(i, j) + string(n - j - i, '*');
// abca
// abc*
// *bca
// ab**
// *bc*
// **ca
// a***
// *b**
// **c*
// ***a
// check if we can use this new_stamp to cover some characters
auto p = target.find(new_stamp);
while (p != string::npos) {
// if so, mark this position
ans.push_back(p);
// and replace those characters
// e.g.
// aabcaca
// a****ca
// a****ca
// a******
// a******
// *******
fill(target.begin() + p, target.begin() + p + n, '*');
// try to find if we can cover another set
p = target.find(new_stamp);
// j is how many characters we've covered
k += j;
}
}
}
// update the total covered characters
total += k;
}
reverse(ans.begin(), ans.end());
return total == target.size() ? ans : vector<int>{};
}
};