Solution: Stamping The Sequence
Tags: algorithms, javascript, python, cpp
Published: 2021-03-31 11:55:17

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/stamping-the-sequence/discuss/1135739).*

---

#### [Leetcode Problem #936 (*Hard*): Stamping The Sequence](https://leetcode.com/problems/stamping-the-sequence/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
You want to form a `target` string of **lowercase letters**.
>
At the beginning, your sequence is `target.length` `'?'` marks.  You also have a `stamp` of **lowercase letters**.
>
On each turn, you may place the stamp over the sequence, and replace every letter in the sequence with the corresponding letter from the stamp.  You can make up to `10 * target.length turns`.
>
For example, if the initial sequence is `"?????"`, and your stamp is `"abc"`,  then you may make `"abc??"`, `"?abc?"`, `"??abc"` in the first turn.  (Note that the stamp must be fully contained in the boundaries of the sequence in order to stamp.)
>
If the sequence is possible to stamp, then return an array of the index of the left-most letter being stamped at each turn.  If the sequence is not possible to stamp, return an empty array.
>
For example, if the sequence is `"ababc"`, and the stamp is `"abc"`, then we could return the answer `[0, 2]`, corresponding to the moves `"?????" -> "abc??" -> "ababc"`.
>
Also, if the sequence is possible to stamp, it is guaranteed it is possible to stamp within `10 * target.length moves`.  Any answers specifying more than this number of moves will not be accepted.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|stamp = "abc", target = "ababc"
Output:|[0,2]<br>([1,0,2] would also be accepted as an answer,<br>as well as some other answers.)
>
Example 2:||
|---:|---|
Input:|stamp = "abca", target = "aabcaca"
Output:|[3,0,1]

---

#### ***Constraints:***
>
 - `1 <= stamp.length <= target.length <= 1000`
 - `stamp` and `target` only contain lowercase letters.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

For this problem, it's easier to think of the target array (**T**) as being composed of layers of stamps (**S**). Since **T** represents the finished product of all the stamps, we'll need to reverse the process and peel off one layer at a time.
```js
 target:  a b a b a b c b c b a b a b c b c


layer 1:          a b c           a b c    
layer 2:      a b c   a b c   a b c   a b c
layer 3:  a b c           a b c
```
So we'll need to iterate through **T** a number of times, finding and removing any full instances of **S**. Once we're past the initial pass, we can use **character masks** to find partial matches for **S** on each remaining pass.
```js
 pass 1:  a b a b a b c b c b a b a b c b c
                  ^ ^ ^           ^ ^ ^

 pass 2:  a b a b * * * b c b a b * * * b c
              ^ ^ ^   ^ ^ ^   ^ ^ ^   ^ ^ ^

 pass 3:  a b * * * * * * * b * * * * * * *
          ^ ^ ^           ^ ^ ^

 pass 4:  * * * * * * * * * * * * * * * * *
```
To speed things up, we should avoid a replacement if the partial match is actually the complete mask (ie, **" * * * "**), as nothing actually changed (**sdiff = false**). Then we should continue until we finish a pass without making any changes (**tdiff = false**).

At that point, if the remaining **T** is all masked, we can return our answer array (**ans**), otherwise we should return an empty array. Since we're locating the stamp indexes in reverse order, we should either insert each newly-found index at the beginning of **ans**, or we should push them to the end and then reverse **ans** before we **return** it.

---

#### ***Implementation:***

Since we need to modify **T**, we should convert it to an array for all except C++, which has mutable strings.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var movesToStamp = function(S, T) {
    if (S === T) return [0]
    let slen = S.length, tlen = T.length - slen + 1,
        ans = [], tdiff = true, sdiff, i, j
    S = S.split(""), T = T.split("")
    while (tdiff)
        for (i = 0, tdiff = false; i < tlen; i++) {
            for (j = 0, sdiff = false; j < slen; j++)
                if (T[i+j] === "*") continue
                else if (T[i+j] !== S[j]) break
                else sdiff = true
            if (j === slen && sdiff) {
                for (j = i, tdiff = true; j < slen + i; j++)
                    T[j] = "*"
                ans.unshift(i)
            }
        }
    for (i = 0; i < T.length; i++) if (T[i] !== "*") return []
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def movesToStamp(self, S: str, T: str) -> List[int]:
        if S == T: return [0]
        S, T = list(S), list(T)
        slen, tlen = len(S), len(T) - len(S) + 1
        ans, tdiff, sdiff = [], True, True
        while tdiff:
            tdiff = False
            for i in range(tlen):
                sdiff = False
                for j in range(slen):
                    if T[i+j] == "*": continue
                    if T[i+j] != S[j]: break
                    sdiff = True
                else: 
                    if sdiff:
                        tdiff = True
                        for j in range(i, i + slen): T[j] = "*"
                        ans.append(i)
        for i in range(len(T)):
            if T[i] != "*": return []
        return reversed(ans)
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int[] movesToStamp(String S, String T) {
        if (S == T) return new int[]{0};
        char[] SC = S.toCharArray(), TC = T.toCharArray();
        int slen = SC.length, tlen = TC.length - slen + 1, i, j;
        List<Integer> lans = new ArrayList<>();
        Boolean tdiff = true, sdiff;
        while (tdiff)
            for (i = 0, tdiff = false; i < tlen; i++) {
                for (j = 0, sdiff = false; j < slen; j++)
                    if (TC[i+j] == '*') continue;
                    else if (TC[i+j] != SC[j]) break;
                    else sdiff = true;
                if (j == slen && sdiff) {
                    for (j = i, tdiff = true; j < slen + i; j++)
                        TC[j] = '*';
                    lans.add(0, i);
                }
            }
        for (i = 0; i < TC.length; i++) if (TC[i] != '*') return new int[]{};
        int[] ans = new int[lans.size()];
        for (i = 0; i < lans.size(); i++) ans[i] = lans.get(i);
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<int> movesToStamp(string S, string T) {
        if (S == T) return {0};
        int slen = S.size(), tlen = T.size() - slen + 1, i, j;
        vector<int> ans;
        bool tdiff = true, sdiff;
        while (tdiff)
            for (i = 0, tdiff = false; i < tlen; i++) {
                for (j = 0, sdiff = false; j < slen; j++)
                    if (T[i+j] == '*') continue;
                    else if (T[i+j] != S[j]) break;
                    else sdiff = true;
                if (j == slen && sdiff) {
                    for (j = i, tdiff = true; j < slen + i; j++)
                        T[j] = '*';
                    ans.push_back(i);
                }
            }
        for (i = 0; i < T.size(); i++) if (T[i] != '*') return {};
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
```