Stamping The Sequence Problem


Description

LeetCode Problem 936.

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:

1
2
3
4
5
6
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:

1
2
3
4
5
6
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.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    // Greedily match stamp with target with offset, ignoring already matched characters.
    vector<int> movesToStamp(string stamp, string target) {
        int NS = stamp.size(), NT = target.size();
        vector<int> ans;
        bool has_match;
        do {
            has_match = false;
            for (int i = 0; i <= NT - NS; i++) {
                bool ok = true;
                int num_dot = 0;
                for (int j = 0; j < NS; j++) { 
                    if (target[i + j] == '.')
                        // take care we don't match only matched ones
                        num_dot++; 
                    if (target[i + j] != '.' && stamp[j] != target[i + j]) { 
                        // simple wildcard matching 
                        ok = false;
                        break;
                    }
                }
                if (ok && num_dot < NS) {
                    has_match = true;
                    ans.push_back(i);
                    for (int j = 0; j < NS; j++) 
                        target[i + j] = '.';
                }
            }

        } while(has_match);
        
        for (char a : target)
            if (a != '.')
                return {};
        reverse(ans.begin(), ans.end());
        return ans;
    }
};




Related Posts

Validate Stack Sequences Problem

LeetCode 946. Given two integer arrays pushed and popped each...

Stamping The Sequence Problem

LeetCode 936. You are given two strings stamp and target....

Score Of Parentheses Problem

LeetCode 856. Given a balanced parentheses string s, return the...

Minimum Add To Make Parentheses Valid Problem

LeetCode 921. A parentheses string is valid if and only...

Maximum Width Ramp Problem

LeetCode 962. A ramp in an integer array nums is...

Decoded String At Index Problem

LeetCode 880. You are given an encoded string s. To...