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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] MovesToStamp(string stamp, string target) {
6 int m = stamp.Length, n = target.Length;
7 char[] targetArr = target.ToCharArray();
8 bool[] visited = new bool[n];
9 List<int> res = new List<int>();
10 int stars = 0;
11
12 while (stars < n) {
13 bool 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 res.Reverse();
27 return res.ToArray();
28 }
29
30 private bool CanStamp(char[] target, char[] stamp, int pos) {
31 for (int i = 0; i < stamp.Length; i++) {
32 if (target[i + pos] != '?' && target[i + pos] != stamp[i])
33 return false;
34 }
35 return true;
36 }
37
38 private int ReplaceWithStar(char[] target, int pos, int length) {
39 int count = 0;
40 for (int i = 0; i < length; i++) {
41 if (target[i + pos] != '?') {
42 target[i + pos] = '?';
43 count++;
44 }
45 }
46 return count;
47 }
48
49 // Example usage
50 public static void Main(string[] args) {
51 Solution sol = new Solution();
52 int[] result = sol.MovesToStamp("abc", "ababc");
53 Console.WriteLine(String.Join(", ", result));
54 }
55}The C# code follows a similar handling of the target and stamp as seen in previous languages. The approach involves converting the target into '?' by strategically stamping based on a match between the stamp and segments in the target. We accumulate results for successful stamps and reverse them to match the correct order required for the problem.