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
50
class Solution {
 public:
  vector<int> movesToStamp(string stamp, string target) {
    vector<int> ans;
    // stamped[i] := true if we already stamped target by stamping on index i
    vector<bool> stamped(target.length());
    int stampedCount = 0;  // Our goal is to make stampedCount = |target|.

    while (stampedCount < target.length()) {
      bool isStamped = false;
      // Try to stamp target[i..i + |stamp|) 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 to stamp on each index, we can't find a valid stamp.
      if (!isStamped)
        return {};
    }

    ranges::reverse(ans);
    return ans;
  }

 private:
  // Stamps target[i..i + |stamp|) and returns the number of newly stamped
  // characters.
  // 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] == '*')  // It's already been stamped.
        --stampified;
      else if (target[s + i] != stamp[i])
        return 0;  // We can't stamp on the index i.

    if (stampified > 0)
      fill(target.begin() + s, target.begin() + 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
48
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 stamping on index i
    boolean[] stamped = new boolean[target.length()];
    int stampedCount = 0; // Our goal is to make stampedCount = |target|.

    while (stampedCount < T.length) {
      boolean isStamped = false;
      // Try to stamp target[i..i + |stamp|) 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 to stamp on each index, we can't find a valid stamp.
      if (!isStamped)
        return new int[] {};
    }

    Collections.reverse(ans);
    return ans.stream().mapToInt(Integer::intValue).toArray();
  }

  // Stamps target[i..i + |stamp|) and returns the number of newly stamped
  // characters.
  // 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] == '*') // It's already been stamped.
        --stampified;
      else if (T[s + i] != stamp.charAt(i))
        return 0; // We can't stamp on the 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
38
39
40
41
42
43
44
45
class Solution:
  def movesToStamp(self, stamp: str, target: str) -> list[int]:
    def stampify(s: int) -> int:
      """
      Stamps target[i..i + |stamp|) and returns the number of newly stamped
      characters.
      e.g. stampify("abc", "ababc", 2) returns 3 because target becomes "ab***".
      """
      stampified = len(stamp)

      for i, st in enumerate(stamp):
        if target[s + i] == '*':  # It's already been stamped.
          stampified -= 1
        elif target[s + i] != st:  # We can't stamp on the index i.
          return 0

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

      return stampified

    ans = []
    target = list(target)
    # stamped[i] := True if we already stamped target by stamping on index i
    stamped = [False] * len(target)
    stampedCount = 0  # Our goal is to make stampedCount = |target|.

    while stampedCount < len(target):
      isStamped = False
      # Try to stamp target[i..i + |stamp|) for each index.
      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)
      # After trying to stamp on each index, we can't find a valid stamp.
      if not isStamped:
        return []

    return ans[::-1]