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.
1import java.util.*;
2
3class Solution {
4 public int[] movesToStamp(String stamp, String target) {
5 int m = stamp.length();
6 int n = target.length();
7 char[] targetArr = target.toCharArray();
8 boolean[] visited = new boolean[n];
9 List<Integer> res = new ArrayList<>();
10 int stars = 0;
11
12 while (stars < n) {
13 boolean stamped = false;
14 for (int i = 0; i <= n - m; i++) {
15 if (!visited[i] && canStamp(targetArr, stamp.toCharArray(), i)) {
16 stars += replaceWithStar(targetArr, i, m);
17 stamped = true;
18 visited[i] = true;
19 res.add(i);
20 if (stars == n) break;
21 }
22 }
23 if (!stamped) return new int[0];
24 }
25
26 int[] resultArr = new int[res.size()];
27 for (int i = 0; i < res.size(); i++) {
28 resultArr[i] = res.get(res.size() - 1 - i);
29 }
30 return resultArr;
31 }
32
33 private boolean canStamp(char[] target, char[] stamp, int pos) {
34 for (int i = 0; i < stamp.length; ++i) {
35 if (target[i + pos] != '?' && target[i + pos] != stamp[i])
36 return false;
37 }
38 return true;
39 }
40
41 private int replaceWithStar(char[] target, int pos, int len) {
42 int count = 0;
43 for (int i = 0; i < len; ++i) {
44 if (target[i + pos] != '?') {
45 target[i + pos] = '?';
46 count++;
47 }
48 }
49 return count;
50 }
51
52 // Example usage
53 public static void main(String[] args) {
54 Solution sol = new Solution();
55 int[] result = sol.movesToStamp("abc", "ababc");
56 System.out.println(Arrays.toString(result));
57 }
58}This Java solution takes a similar approach by using character arrays for the target and the stamp. The idea is to stamp out the target in reverse, meaning we will start with the full target and work our way to the all '?'. Each successful stamp operation reduces the number of non-'?' characters and effectively adds to our result list that is reversed at the end to be the correct sequence.