Stamping The Sequence — LeetCode 936 Python Solution
HardStackGreedyQueueString
- Problem
- #936
- Pattern
- Stack
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'.
Example
- Input
- stamp = "abc", target = "ababc"
- Output
- [0,2]
- Explanation
- Initially s = "?????".
Python solution
Python
class Solution:
def movesToStamp(self, stamp: str, target: str) -> List[int]:
m, n = len(stamp), len(target)
indeg = [m] * (n - m + 1)
q = deque()
g = [[] for _ in range(n)]
for i in range(n - m + 1):
for j, c in enumerate(stamp):
if target[i + j] == c:
indeg[i] -= 1
if indeg[i] == 0:
q.append(i)
else:
g[i + j].append(i)
ans = []
vis = [False] * n
while q:
i = q.popleft()
ans.append(i)
for j in range(m):
if not vis[i + j]:
vis[i + j] = True
for k in g[i + j]:
indeg[k] -= 1
if indeg[k] == 0:
q.append(k)
return ans[::-1] if all(vis) else []Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times (n - m + 1)) |
| Space | O(n \times (n - m + 1)) auxiliary |
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 936. Stamping The Sequence is filed here because LeetCode tags it Stack and Queue, which is the vocabulary this hub collects.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 936. Stamping The Sequence?
- LeetCode 936. Stamping The Sequence is rated Hard on LeetCode.
- What is the time complexity of LeetCode 936. Stamping The Sequence?
- The Python solution on this page runs in O(n \times (n - m + 1)).
- What is the space complexity of LeetCode 936. Stamping The Sequence?
- The Python solution on this page uses O(n \times (n - m + 1)) auxiliary space.
- What topics does LeetCode 936. Stamping The Sequence cover?
- LeetCode 936. Stamping The Sequence is tagged Stack, Greedy, Queue and String on LeetCode.