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.
1function movesToStamp(stamp, target) {
2 const m = stamp.length, n = target.length;
3 const targetArr = target.split('');
4 const visited = Array(n).fill(false);
5 const res = [];
6 let stars = 0;
7
8 const canStamp = (pos) => {
9 for (let i = 0; i < m; i++) {
10 if (targetArr[i + pos] !== '?' && targetArr[i + pos] !== stamp[i])
11 return false;
12 }
13 return true;
14 };
15
16 const replaceWithStar = (pos) => {
17 let count = 0;
18 for (let i = 0; i < m; i++) {
19 if (targetArr[i + pos] !== '?') {
20 targetArr[i + pos] = '?';
21 count++;
22 }
23 }
24 return count;
25 };
26
27 while (stars < n) {
28 let stamped = false;
29 for (let i = 0; i <= n - m; i++) {
30 if (!visited[i] && canStamp(i)) {
31 stars += replaceWithStar(i);
32 stamped = true;
33 visited[i] = true;
34 res.push(i);
35 if (stars === n) break;
36 }
37 }
38 if (!stamped) return [];
39 }
40
41 return res.reverse();
42}
43
44// Example usage
45const result = movesToStamp("abc", "ababc");
46console.log(result);The JavaScript solution iterates over possible stamping positions in the target string, replacing matching sections with '?' until the whole string is reduced to '?'. Each successful stamping operation is recorded and the sequence is reversed in the end to reflect the order of transformations needed to achieve this state.