Skip to content

936. Stamping The Sequence

Difficulty Topics

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" and target = "abcba", then s is "?????" initially. In one turn you can:
    • place stamp at index 0 of s to obtain "abc??",
    • place stamp at index 1 of s to obtain "?abc?", or
    • place stamp at index 2 of s to obtain "??abc".
    Note that stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s).

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 and target consist of lowercase English letters.

Solution

stamping-the-sequence.py
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 []