# 936. Stamping The Sequence

#### Hard

***

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:

  ```
  <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.

&#x20;

**Example 1:**

<pre><code>Input: stamp = "abc", target = "ababc"
<strong>Output:
</strong> [0,2]
<strong>Explanation:
</strong> 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.
</code></pre>

**Example 2:**

<pre><code>Input: stamp = "abca", target = "aabcaca"
<strong>Output:
</strong> [3,0,1]
<strong>Explanation:
</strong> 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></pre>

&#x20;

**Constraints:**

* `1 <= stamp.length <= target.length <= 1000`
* `stamp` and `target` consist of lowercase English letters.

```python
class Solution:
#.
    def movesToStamp(self, stamp, target):
        def okay(s):
            ret = False
            for c1, c2 in zip(s, stamp):
                if c1 == "?": continue
                elif c1 != c2: return False
                else: ret = True
            return ret
        root, move, mx, arr = "?" * len(target), 0, 10 * len(target), []
        while move < mx:
            pre = move
            for i in range(len(target) - len(stamp) + 1):
                if okay(target[i:i + len(stamp)]):
                    move += 1
                    arr = [i] + arr
                    target = target[:i] + "?" * len(stamp) + target[i + len(stamp):]
            if target == root: return arr
            if move == pre: break
        return []
```