#936
Stamping The Sequence
expert · 1145 · lc hard +32 · verified · 62.2% accepted · 1,578 likes · top 63%
Description
You are given strings stamp and target. Begin with a string s of target.length question marks. Each move places stamp aligned at a chosen starting index in s, overwriting those characters. Find a sequence of at most 10 * target.length starting positions such that the moves transform s into target, and return the positions in reverse chronological order.
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".
Code
1
2
3