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.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4#include <stdbool.h>
5
6#define MAX_TURNS 10000
7
8bool canStamp(char *target, char *stamp, int pos) {
9 for (int i = 0; i < strlen(stamp); i++) {
10 if (target[pos + i] != '?' && target[pos + i] != stamp[i]) {
11 return false;
12 }
13 }
14 return true;
15}
16
17int doStamp(char *target, char *stamp, int pos) {
18 int stamped = 0;
19 for (int i = 0; i < strlen(stamp); i++) {
20 if (target[pos + i] != '?') {
21 target[pos + i] = '?';
22 stamped++;
23 }
24 }
25 return stamped;
26}
27
28int *movesToStamp(char *stamp, char *target, int *returnSize) {
29 int stampLen = strlen(stamp);
30 int targetLen = strlen(target);
31 int *res = (int *)malloc(sizeof(int) * MAX_TURNS);
32 *returnSize = 0;
33 int stamped;
34 int totalStamped = 0;
35 bool stampedSomething;
36
37 do {
38 stampedSomething = false;
39 for (int i = 0; i <= targetLen - stampLen; i++) {
40 if (canStamp(target, stamp, i)) {
41 stamped = doStamp(target, stamp, i);
42 if (stamped > 0) {
43 res[(*returnSize)++] = i;
44 stampedSomething = true;
45 totalStamped += stamped;
46 if (totalStamped == targetLen) {
47 break;
48 }
49 }
50 }
51 }
52 } while (stampedSomething && totalStamped < targetLen);
53
54 if (totalStamped < targetLen) {
55 *returnSize = 0;
56 free(res);
57 return NULL;
58 }
59
60 for (int i = 0; i < *returnSize / 2; ++i) {
61 int temp = res[i];
62 res[i] = res[*returnSize - i - 1];
63 res[*returnSize - i - 1] = temp;
64 }
65
66 return res;
67}
68
69int main() {
70 int returnSize;
71 char stamp[] = "abc";
72 char target[] = "ababc";
73 int* result = movesToStamp(stamp, target, &returnSize);
74 printf("[");
75 for (int i = 0; i < returnSize; i++) {
76 printf("%d%s", result[i], (i == returnSize - 1) ? "" : ", ");
77 }
78 printf("]\n");
79 free(result);
80 return 0;
81}This solution works by simulating the stamping as a process of replacing portions of the target string with '?'. This approach checks all possible positions to stamp and only performs stamping if the stamp can fully 'cover' or 'match' the target at the current position without introducing 'new' unmatched characters. The process continues until the whole target is replaced with '?'.
Each time we successfully stamp a portion, we accumulate that index in our results and later reverse the results to match the sequence from initial stamping to the final target.