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:<ul> <li>place <code>stamp</code> at index <code>0</code> of <code>s</code> to obtain <code>"abc??"</code>,</li> <li>place <code>stamp</code> at index <code>1</code> of <code>s</code> to obtain <code>"?abc?"</code>, or</li> <li>place <code>stamp</code> at index <code>2</code> of <code>s</code> to obtain <code>"??abc"</code>.</li> </ul> Note that <code>stamp</code> must be fully contained in the boundaries of <code>s</code> in order to stamp (i.e., you cannot place <code>stamp</code> at index <code>3</code> of <code>s</code>).</li>
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.
Solution
Python3
class Solution:
def movesToStamp(self, S: str, T: str) -> List[int]:
if S == T: return [0]
S, T = list(S), list(T)
sn, tn = len(S), len(T)
res = []
sDiff = tDiff = True
while tDiff:
tDiff = False
for i in range(tn - sn + 1):
sDiff = False
for j in range(sn):
if T[i + j] == "*": continue
if T[i + j] != S[j]: break
sDiff = True
else:
if sDiff:
for j in range(i, i + sn):
T[j] = "*"
tDiff = True
res.append(i)
return reversed(res) if all(c == "*" for c in T) else []