0936. Stamping The Sequence
https://leetcode.com/problems/stamping-the-sequence
Description
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"
, thens
is"?????"
initially. In one turn you can:place
stamp
at index0
ofs
to obtain"abc??"
,place
stamp
at index1
ofs
to obtain"?abc?"
, orplace
stamp
at index2
ofs
to obtain"??abc"
. Note thatstamp
must be fully contained in the boundaries ofs
in order to stamp (i.e., you cannot placestamp
at index3
ofs
).
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 <= 1000
stamp
andtarget
consist of lowercase English letters.
ac
Last updated
Was this helpful?