Leetcode 936. Stamping The Sequence
Problem Explanation
You are given a string (target
) and a sequence of characters (stamp
). At first, the target
string is completely hidden, represented by ?
marks. The aim is to reveal the target
string by applying the stamp
repeatedly against the target
string. On each turn, you may place the stamp over the mask (a substring of the hidden string), and replace every mark in the sequence with the corresponding character from the stamp
. You are not limited to stamping from left to right -- you can use a stamp anywhere on the current sequence. If stamping is possible, return the sequence of indices on the target string where the leftmost character of the stamp is applied at each turn. If target
string cannot be formed by stamping, return an empty list.
As an example: Input: stamp = "abc", target = "ababc" At the first step, we can stamp on the first 3 characters, so our operation is "?????" -> "abc??". The index of the left-most letter being stamped at this turn is 0. At the second step, we can stamp on last 3 characters, so our operation is "abc??" -> "ababc". The index of the left-most letter being stamped at this turn is 2. So, we return [0,2] for this example. Other valid outputs would be [0,1,2] or [1,0,2].
Solution Explanation
The solution uses a greedy algorithm. The key observation is that for any overlap between two stamps, the stamp applied later must cover an unchanged part of the target string and a previously stamped part. Therefore, we should focus on applying stamps on the leftmost still unchanged parts, which means we are applying stamps in reverse order. The algorithm begins from the rightmost part of the target string, tries to match the stamp starting from each position i in the target, and if possible, replaces the matched part of the target string with *
characters and records this position i. We repeat this process until we cannot stamp out a new substring, then reverse our answer and return it.
1
2text
3ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย Initial target: ??????
4Abc at 2nd position : ????abc -> ??abcabc -> ?abcabc* -> Abcabc**
5Abc at 0th position : Abcabc** -> **abcabc*
6Abc at 0th position : **abcabc* -> *****abc
7Abc at 3rd position : *****abc -> ********
Python Solution
1 2python 3class Solution: 4 def movesToStamp(self, stamp: str, target: str) -> List[int]: 5 # Initialize variables 6 stamp = list(stamp) 7 target = list(target) 8 stamp_len = len(stamp) 9 target_len = len(target) 10 visited = [False]*target_len 11 ans = [] 12 13 def can_stamp(start): 14 # Check if we can apply the stamp at this position 15 i = start 16 j = 0 17 stamped = False 18 while j<stamp_len and i<target_len: 19 if target[i] == '?': 20 i += 1 21 j += 1 22 elif target[i] == stamp[j]: 23 i += 1 24 j += 1 25 stamped = True 26 else: 27 return False 28 if j == stamp_len: 29 return stamped 30 return False 31 32 # Try to apply the stamp at each position 33 for _ in range(target_len): 34 for i in range(target_len-stamp_len+1): 35 # If this position is not visited and we can stamp at this position 36 if not visited[i] and can_stamp(i): 37 # Apply the stamp 38 for j in range(i,i+stamp_len): 39 target[j] = '?' 40 # Note that we visited this position 41 visited[i] = True 42 ans.append(i) 43 break 44 # If we cannot stamp anymore, just break 45 else: 46 break 47 48 # Check if we stamped the whole target successfully 49 if all(c == '?' for c in target): 50 ans.reverse() 51 return ans 52 else: 53 return []
Java Solution
For solutions in other languages like Java, Javascript, C++, C#, the overall algorithm doesn't change. I am providing the Java solution below with similar comments for better understanding.
1 2java 3class Solution { 4 public int[] movesToStamp(String stamp, String target) { 5 char[] s = stamp.toCharArray(); 6 char[] t = target.toCharArray(); 7 List<Integer> res = new ArrayList<>(); 8 boolean[] visit = new boolean[t.length]; 9 int stars = 0; 10 11 while (stars < t.length) { 12 boolean doneReplace = false; 13 for (int i = 0; i <= t.length - s.length; i++) { 14 if (!visit[i] && canReplace(t, i, s)) { 15 stars = doReplace(t, i, s.length, stars); 16 doneReplace = true; 17 res.add(i); 18 visit[i] = true; 19 20 if (stars == t.length) { 21 break; 22 } 23 } 24 } 25 26 if (!doneReplace) { 27 return new int[0]; 28 } 29 } 30 31 int[] ans = new int[res.size()]; 32 for (int i = 0; i < res.size(); i++) { 33 ans[i] = res.get(res.size() - 1 - i); 34 } 35 return ans; 36 } 37 38 private boolean canReplace(char[] t, int p, char[] s) { 39 for (int i = 0; i < s.length; i++) { 40 if (t[i + p] != '*' && t[i + p] != s[i]) { 41 return false; 42 } 43 } 44 return true; 45 } 46 47 private int doReplace(char[] t, int p, int len, int count) { 48 for (int i = 0; i < len; i++) { 49 if (t[i + p] != '*') { 50 t[i + p] = '*'; 51 count++; 52 } 53 } 54 return count; 55 } 56}
Notice for each language the function or method that checks if we can apply the stamp
at a given position and the function or method that applies the stamp
at that position and marks it as visited, is the center of attention. Then the greedy algorithm comes into play where we apply the stamp at any valid position we can find until we can't anymore, then we check if the whole string is stamped out.# JavaScript Solution
Implementing the solution in JavaScript, we use the functionality of Array.prototype.every() method and Array.prototype.slice() method for processing the arrays representing the string inputs.
1 2javascript 3var movesToStamp = function(stamp, target) { 4 let t = target.split(''), s = stamp.split(''); 5 let tlen = t.length, slen = s.length, res = [], turn; 6 let done = Array(tlen).fill(false); 7 let total = 0; 8 9 const canReplace = (t, i, s, changeToStar) => { 10 let replaced = false; 11 for(let j = 0; j < slen; j++) { 12 if(t[i+j] === '?') { 13 continue; 14 } 15 if(t[i+j] !== s[j]) { 16 return false; 17 } 18 if(!changeToStar) { 19 replaced = true; 20 } else { 21 t[i+j] = '?'; 22 } 23 } 24 return replaced; 25 } 26 27 do { 28 turn = false; 29 for(let i = 0; i <= tlen - slen; i++) { 30 if(!done[i] && canReplace(t, i, s, false)) { 31 total += slen; 32 turn = done[i] = true; 33 res.push(i); 34 canReplace(t, i, s, true); 35 } 36 } 37 } while(turn && total < tlen ) 38 39 if(total === tlen) { 40 return res.reverse(); 41 } else { 42 return []; 43 } 44};
In the JavaScript solution, we use the JavaScript function split()
to convert the target and stamp strings into arrays of characters, t
and s
respectively. These arrays are then processed in the canReplace()
function which checks if we can apply the stamp
at a given position and also applies the stamp
at that position. Like the other solutions, this solution employs a greedy algorithm to identify valid positions for stamp
application until none can be found. Finally, the function checks whether the entire target string has been stamped out. If it has, the function returns the positions at which the stamp
was applied in reverse order; if not, it returns an empty array.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.