# 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 movesToStamp(string stamp, string target) { vector ans; // stamped[i] := true if we already stamped target by stamp on index i vector 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 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]