In this guide, you will get 936. Stamping The Sequence LeetCode Solution with the best time and space complexity. The solution to Stamping The Sequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == ‘?’.
In one turn, you can place stamp over s and replace every letter in the s with the corresponding letter from stamp.
For example, if stamp = “abc” and target = “abcba”, then s is “?????” initially. In one turn you can:
place stamp at index 0 of s to obtain “abc??”,
place stamp at index 1 of s to obtain “?abc?”, or
place stamp at index 2 of s to obtain “??abc”.
Note that stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s).
We want to convert s to target using at most 10 * target.length turns.
Return an array of the index of the left-most letter being stamped at each turn. If we cannot obtain target from s within 10 * target.length turns, return an empty array.
Example 1:
Input: stamp = “abc”, target = “ababc”
Output: [0,2]
Explanation: Initially s = “?????”.
– Place stamp at index 0 to get “abc??”.
– Place stamp at index 2 to get “ababc”.
[1,0,2] would also be accepted as an answer, as well as some other answers.
Input: stamp = “abca”, target = “aabcaca”
Output: [3,0,1]
Explanation: Initially s = “???????”.
– Place stamp at index 3 to get “???abca”.
– Place stamp at index 0 to get “abcabca”.
– Place stamp at index 1 to get “aabcaca”.
Constraints:
1 <= stamp.length <= target.length <= 1000
stamp and target consist of lowercase English letters.
Complexity Analysis
Time Complexity: O((|\texttt{target}| – |\texttt{stamp}|)^2 \cdot |\texttt{stamp}|)
Space Complexity: O(|\texttt{target}|)
936. Stamping The Sequence LeetCode Solution in C++
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
vector<int> ans;
// stamped[i] := true if we already stamped target by stamping on index i
vector<bool> stamped(target.length());
int stampedCount = 0; // Our goal is to make stampedCount = |target|.
while (stampedCount < target.length()) {
bool isStamped = false;
// Try to stamp target[i..i + |stamp|) for each index.
for (int i = 0; i <= target.length() - stamp.length(); ++i) {
if (stamped[i])
continue;
const int stampified = stampify(stamp, target, i);
if (stampified == 0)
continue;
stampedCount += stampified;
isStamped = true;
stamped[i] = true;
ans.push_back(i);
}
// After trying to stamp on each index, we can't find a valid stamp.
if (!isStamped)
return {};
}
ranges::reverse(ans);
return ans;
}
private:
// Stamps target[i..i + |stamp|) and returns the number of newly stamped
// characters.
// e.g. stampify("abc", "ababc", 2) returns 3 because target becomes "ab***".
int stampify(const string& stamp, string& target, int s) {
int stampified = stamp.length();
for (int i = 0; i < stamp.length(); ++i)
if (target[s + i] == '*') // It's already been stamped.
--stampified;
else if (target[s + i] != stamp[i])
return 0; // We can't stamp on the index i.
if (stampified > 0)
fill(target.begin() + s, target.begin() + s + stamp.length(), '*');
return stampified;
}
}; /* code provided by PROGIEZ */
936. Stamping The Sequence LeetCode Solution in Java
class Solution {
public int[] movesToStamp(String stamp, String target) {
List<Integer> ans = new ArrayList<>();
char[] T = target.toCharArray();
// stamped[i] := true if we already stamped target by stamping on index i
boolean[] stamped = new boolean[target.length()];
int stampedCount = 0; // Our goal is to make stampedCount = |target|.
while (stampedCount < T.length) {
boolean isStamped = false;
// Try to stamp target[i..i + |stamp|) for each index.
for (int i = 0; i <= T.length - stamp.length(); ++i) {
if (stamped[i])
continue;
final int stampified = stampify(stamp, T, i);
if (stampified == 0)
continue;
stampedCount += stampified;
isStamped = true;
stamped[i] = true;
ans.add(i);
}
// After trying to stamp on each index, we can't find a valid stamp.
if (!isStamped)
return new int[] {};
}
Collections.reverse(ans);
return ans.stream().mapToInt(Integer::intValue).toArray();
}
// Stamps target[i..i + |stamp|) and returns the number of newly stamped
// characters.
// e.g. stampify("abc", "ababc", 2) returns 3 because target becomes "ab***".
private int stampify(final String stamp, char[] T, int s) {
int stampified = stamp.length();
for (int i = 0; i < stamp.length(); ++i)
if (T[s + i] == '*') // It's already been stamped.
--stampified;
else if (T[s + i] != stamp.charAt(i))
return 0; // We can't stamp on the index i.
Arrays.fill(T, s, s + stamp.length(), '*');
return stampified;
}
} // code provided by PROGIEZ
936. Stamping The Sequence LeetCode Solution in Python
class Solution:
def movesToStamp(self, stamp: str, target: str) -> list[int]:
def stampify(s: int) -> int:
"""
Stamps target[i..i + |stamp|) and returns the number of newly stamped
characters.
e.g. stampify("abc", "ababc", 2) returns 3 because target becomes "ab***".
"""
stampified = len(stamp)
for i, st in enumerate(stamp):
if target[s + i] == '*': # It's already been stamped.
stampified -= 1
elif target[s + i] != st: # We can't stamp on the index i.
return 0
for i in range(s, s + len(stamp)):
target[i] = '*'
return stampified
ans = []
target = list(target)
# stamped[i] := True if we already stamped target by stamping on index i
stamped = [False] * len(target)
stampedCount = 0 # Our goal is to make stampedCount = |target|.
while stampedCount < len(target):
isStamped = False
# Try to stamp target[i..i + |stamp|) for each index.
for i in range(len(target) - len(stamp) + 1):
if stamped[i]:
continue
stampified = stampify(i)
if stampified == 0:
continue
stampedCount += stampified
isStamped = True
stamped[i] = True
ans.append(i)
# After trying to stamp on each index, we can't find a valid stamp.
if not isStamped:
return []
return ans[::-1] # code by PROGIEZ
