936. Stamping The Sequence
Explanation:
To solve this problem, we can use a greedy algorithm approach. We will repeatedly try to stamp the target string with the stamp, and each time we successfully stamp part of the target, we update the target string and record the index of the left-most letter being stamped.
- Initially, we create a set to store all the indices where we can stamp the target with the stamp.
- We repeat the following steps until the target becomes all stamped or we reach the maximum allowed turns:
- Iterate over the target string and check if the stamp can be placed starting at each index.
- If the stamp can be placed at a particular index, update the target string by stamping the characters and add the index to the set of stamped indices.
- If the target becomes all stamped, return the stamped indices in reverse order (as we are stamping from the end to the beginning). Otherwise, return an empty array.
:
class Solution {
public int[] movesToStamp(String stamp, String target) {
char[] s = target.toCharArray();
char[] t = stamp.toCharArray();
int S = s.length, T = t.length;
List<Integer> stamped = new ArrayList<>();
boolean[] visited = new boolean[S];
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i <= S - T; i++) {
boolean match = false;
for (int j = 0; j < T; j++) {
if (s[i + j] == t[j] || s[i + j] == '?') {
match = true;
} else {
match = false;
break;
}
}
if (match) {
changed = true;
for (int j = 0; j < T; j++) {
if (s[i + j] != '?') {
s[i + j] = '?';
stamped.add(i + j);
}
}
for (int k = 0; k < S; k++) {
visited[k] = visited[k] || i <= k && k < i + T;
}
}
}
}
for (int i = 0; i < S; i++) {
if (!visited[i] && s[i] != '?') return new int[0];
}
int[] result = new int[stamped.size()];
for (int i = 0; i < stamped.size(); i++) {
result[i] = stamped.get(stamped.size() - 1 - i);
}
return result;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.