Sponsored
Sponsored
This approach involves reversing the stamping process. Instead of trying to form the target from '?' gradually, we attempt to convert the target into '?' by 'un-stamping' in a greedy way.
We can try and 'stamp out' the pattern from the target where it matches. This continues until we've stamped out the entire target or until we determine it's impossible to do so within the given constraints.
Time Complexity: O((N-M+1)*M) where N is the length of target and M is the length of stamp. We effectively iterate through the length of the target and for each possible stamping position, we may iterate through the stamp.
Space Complexity: O(N) to hold the result of the stampping sequence.
1from typing import List
2
3class Solution:
4 def movesToStamp(self, stamp: str, target: str) -> List[int]:
5 m, n = len(stamp), len(target)
6 target = list(target)
7 visited = [False] * n
8 res = []
9 stars = 0
10
11 def canStamp(pos: int) -> bool:
12 for i in range(m):
13 if target[i + pos] != '?' and target[i + pos] != stamp[i]:
14 return False
15 return True
16
17 def replaceWithStar(pos: int) -> int:
18 count = 0
19 for i in range(m):
20 if target[i + pos] != '?':
21 target[i + pos] = '?'
22 count += 1
23 return count
24
25 while stars < n:
26 stamped = False
27 for i in range(n - m + 1):
28 if not visited[i] and canStamp(i):
29 stars += replaceWithStar(i)
30 stamped = True
31 visited[i] = True
32 res.append(i)
33 if stars == n:
34 break
35 if not stamped:
36 return []
37
38 return res[::-1]
39
40# Example usage
41sol = Solution()
42result = sol.movesToStamp("abc", "ababc")
43print(result)The Python implementation uses a list to track the positions that can potentially be converted to '?' by successful stamping. It iterates over possible positions, replaces segments matching the stamp criteria, and then checks if the entire target can become '?'. It appends successfully stamped indices to a list that represents the reverse path of stamping.