Stamping The Sequence
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 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?". - Place
stampat index2ofsto obtain"??abc". - Note that
stampmust be fully contained in the boundaries ofsin order to stamp; that is, you cannot placestampat index3ofsin the example above.
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]Placing the stamp at index 0 produces "abc??", then placing it at index 2 produces "ababc"; other valid sequences may also be accepted.
Example 2
Input
stamp = "abca", target = "aabcaca"Output
[3,0,1]Placing the stamp at indices 3, 0, and 1 transforms the initial question marks into "aabcaca".
Constraints
- 1 <= stamp.length <= target.length <= 1000
- stamp and target consist of lowercase English letters.