## Algorithm

Problem Name: 936. Stamping The Sequence

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.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[] movesToStamp(String stamp, String target) {
char[] stampLetters = stamp.toCharArray();
char[] targetLetters = target.toCharArray();
List result = new ArrayList<>();
boolean[] visited = new boolean[target.length()];
int count = 0;
while (count < target.length()) {
boolean replace = false;
for (int i = 0; i <= target.length() - stamp.length(); i++) {
if (!visited[i] && isReplacePossible(stampLetters, targetLetters, i)) {
count = performStamping(targetLetters, i, stamp.length(), count);
replace = true;
visited[i] = true;
if (count == targetLetters.length) {
break;
}
}
}
if (!replace) {
return new int;
}
}
int[] resArray = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
resArray[i] = result.get(result.size() - i - 1);
}
return resArray;
}

private boolean isReplacePossible(char[] stampLetters, char[] targetLetters, int idx) {
for (int i = 0; i < stampLetters.length; i++) {
if (targetLetters[i + idx] != '*' && targetLetters[i + idx] != stampLetters[i]) {
return false;
}
}
return true;
}

private int performStamping(char[] targetLetters, int idx, int stampLength, int count) {
for (int i = 0; i < stampLength; i++) {
if (targetLetters[i + idx] != '*') {
targetLetters[i + idx] = '*';
count++;
}
}
return count;
}
}
``````
Copy The Code &

Input

cmd
stamp = "abc", target = "ababc"

Output

cmd
[0,2]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const movesToStamp = function (stamp, target) {
const S = stamp.split('')
const T = target.split('')
const res = []
const visited = Array(T.length).fill(false)
let stars = 0

while (stars < T.length) {
let doneReplace = false
for (let i = 0; i <= T.length - S.length; i++) {
if (!visited[i] && canReplace(T, i, S)) {
stars = doReplace(T, i, S.length, stars)
doneReplace = true
visited[i] = true
res.unshift(i)
if (stars === T.length) {
break
}
}
}

if (!doneReplace) {
return []
}
}

return res
function canReplace(T, p, S) {
for (let i = 0; i < S.length; i++) {
if (T[i + p] !== '*' && T[i + p] !== S[i]) {
return false
}
}
return true
}

function doReplace(T, p, len, count) {
for (let i = 0; i < len; i++) {
if (T[i + p] !== '*') {
T[i + p] = '*'
count++
}
}
return count
}
}
``````
Copy The Code &

Input

cmd
stamp = "abc", target = "ababc"

Output

cmd
[0,2]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
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
t, 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 == t: return arr
if move == pre: break
return []
``````
Copy The Code &

Input

cmd
stamp = "abca", target = "aabcaca"

Output

cmd
[3,0,1]