DEV Community

Cover image for Solution: Stamping The Sequence
seanpgallivan
seanpgallivan

Posted on

Solution: Stamping The Sequence

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.


Leetcode Problem #936 (Hard): Stamping The Sequence


Description:


(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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]
([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]

Constraints:

  • 1 <= stamp.length <= target.length <= 1000
  • stamp and target only contain lowercase letters.

Idea:


(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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.

 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
Enter fullscreen mode Exit fullscreen mode

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.

 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:  * * * * * * * * * * * * * * * * *
Enter fullscreen mode Exit fullscreen mode

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:


(Jump to: Problem Description || Solution Idea)

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
};
Enter fullscreen mode Exit fullscreen mode

Python Code:


(Jump to: Problem Description || Solution Idea)

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)
Enter fullscreen mode Exit fullscreen mode

Java Code:


(Jump to: Problem Description || Solution Idea)

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

C++ Code:


(Jump to: Problem Description || Solution Idea)

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)