Skip to content

936. Stamping The Sequence 👍

  • Time: $O((|\texttt{target}| - |\texttt{stamp}|)^2 \cdot |\texttt{stamp}|)$
  • Space: $O(|\texttt{target}|)$
 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
40
41
42
43
44
45
46
47
48
49
class Solution {
 public:
  vector<int> movesToStamp(string stamp, string target) {
    vector<int> ans;
    // stamped[i] := true if we already stamped target by stamp on index i
    vector<bool> stamped(target.length());
    int stampedCount = 0;  // out goal is to make stampedCount = target.length()

    while (stampedCount < target.length()) {
      bool isStamped = false;
      // try to stamp target[i..i + stamp.length()) for each index
      for (int i = 0; i <= target.length() - stamp.length(); ++i) {
        if (stamped[i])
          continue;
        const int stampified = stampify(stamp, target, i);
        if (stampified == 0)
          continue;
        stampedCount += stampified;
        isStamped = true;
        stamped[i] = true;
        ans.push_back(i);
      }
      // after trying stamp each index, we can't find a valid stamp
      if (!isStamped)
        return {};
    }

    reverse(begin(ans), end(ans));
    return ans;
  }

 private:
  // stamp target[i..i + stamp.length()) and return # of newly stamped chars
  // e.g. stampify("abc", "ababc", 2) returns 3 because target becomes "ab***"
  int stampify(const string& stamp, string& target, int s) {
    int stampified = stamp.length();

    for (int i = 0; i < stamp.length(); ++i)
      if (target[s + i] == '*')  // already stamped
        --stampified;
      else if (target[s + i] != stamp[i])
        return 0;  // we can't stamp on index i

    if (stampified > 0)
      fill(begin(target) + s, begin(target) + s + stamp.length(), '*');

    return stampified;
  }
};

 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
40
41
42
43
44
45
46
47
class Solution {
  public int[] movesToStamp(String stamp, String target) {
    List<Integer> ans = new ArrayList<>();
    char[] T = target.toCharArray();
    // stamped[i] := true if we already stamped target by stamp on index i
    boolean[] stamped = new boolean[target.length()];
    int stampedCount = 0; // out goal is to make stampedCount = target.length()

    while (stampedCount < T.length) {
      boolean isStamped = false;
      // try to stamp target[i..i + stamp.length()) for each index
      for (int i = 0; i <= T.length - stamp.length(); ++i) {
        if (stamped[i])
          continue;
        final int stampified = stampify(stamp, T, i);
        if (stampified == 0)
          continue;
        stampedCount += stampified;
        isStamped = true;
        stamped[i] = true;
        ans.add(i);
      }
      // after trying stamp each index, we can't find a valid stamp
      if (!isStamped)
        return new int[] {};
    }

    Collections.reverse(ans);
    return ans.stream().mapToInt(i -> i).toArray();
  }

  // stamp target[i..i + stamp.length()) and return # of newly stamped chars
  // e.g. stampify("abc", "ababc", 2) returns 3 because target becomes "ab***"
  private int stampify(final String stamp, char[] T, int s) {
    int stampified = stamp.length();

    for (int i = 0; i < stamp.length(); ++i)
      if (T[s + i] == '*') // already stamped
        --stampified;
      else if (T[s + i] != stamp.charAt(i))
        return 0; // we can't stamp on index i

    Arrays.fill(T, s, s + stamp.length(), '*');

    return stampified;
  }
}

 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
class Solution:
  def movesToStamp(self, stamp: str, target: str) -> List[int]:
    def stampify(s: int) -> int:
      stampified = len(stamp)

      for i, st in enumerate(stamp):
        if target[s + i] == '*':
          stampified -= 1
        elif target[s + i] != st:
          return 0

      for i in range(s, s + len(stamp)):
        target[i] = '*'

      return stampified

    ans = []
    target = list(target)
    stamped = [False] * len(target)
    stampedCount = 0

    while stampedCount < len(target):
      isStamped = False
      for i in range(len(target) - len(stamp) + 1):
        if stamped[i]:
          continue
        stampified = stampify(i)
        if stampified == 0:
          continue
        stampedCount += stampified
        isStamped = True
        stamped[i] = True
        ans.append(i)
      if not isStamped:
        return []

    return ans[::-1]
Back to top