LeetCode 题解工作台
戳印序列
你想要用 小写字母 组成一个目标字符串 target 。 开始的时候，序列由 target.length 个 '?' 记号组成。而你有一个小写字母印章 stamp 。 在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行 10 * target.length…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
如果我们正向地对序列进行操作，那么处理起来会比较麻烦，因为后续的操作会把前面的操作覆盖掉。我们不妨考虑逆向地对序列进行操作，即从目标字符串 开始，考虑将 变成 的过程。 我们不妨记字母印章的长度为 ，目标字符串的长度为 。如果我们拿着字母印章在目标字符串上操作，那么一共有 个开始位置可以放置字母印章。我们可以枚举这 个开始位置，利用类似拓扑排序的方法，逆向地进行操作。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
你想要用小写字母组成一个目标字符串 target。
开始的时候，序列由 target.length 个 '?' 记号组成。而你有一个小写字母印章 stamp。
在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行 10 * target.length 个回合。
举个例子，如果初始序列为 "?????"，而你的印章 stamp 是 "abc"，那么在第一回合，你可以得到 "abc??"、"?abc?"、"??abc"。（请注意，印章必须完全包含在序列的边界内才能盖下去。）
如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。
例如，如果序列是 "ababc"，印章是 "abc"，那么我们就可以返回与操作 "?????" -> "abc??" -> "ababc" 相对应的答案 [0, 2]；
另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成。任何超过此数字的答案将不被接受。
示例 1：
输入：stamp = "abc", target = "ababc" 输出：[0,2] （[1,0,2] 以及其他一些可能的结果也将作为答案被接受）
示例 2：
输入：stamp = "abca", target = "aabcaca" 输出：[3,0,1]
提示：
1 <= stamp.length <= target.length <= 1000stamp和target只包含小写字母。
解题思路
方法一：逆向思维 + 拓扑排序
如果我们正向地对序列进行操作，那么处理起来会比较麻烦，因为后续的操作会把前面的操作覆盖掉。我们不妨考虑逆向地对序列进行操作，即从目标字符串 开始，考虑将 变成 的过程。
我们不妨记字母印章的长度为 ，目标字符串的长度为 。如果我们拿着字母印章在目标字符串上操作，那么一共有 个开始位置可以放置字母印章。我们可以枚举这 个开始位置，利用类似拓扑排序的方法，逆向地进行操作。
首先，我们明确，每个开始位置都对应着一个长度为 的窗口。
接下来，我们定义以下数据结构或变量，其中：
- 入度数组 ，其中 表示第 个窗口中有多少位置的字符与字母印章中的字符不同，初始时，。若 ，说明第 个窗口中的字符都与字母印章中的字符相同，那么我们就可以在第 个窗口中放置字母印章。
- 邻接表 ，其中 表示目标字符串 的第 个位置上，所有与字母印章存在不同字符的窗口的集合。
- 队列 ，用于存储所有入度为 的窗口的编号。
- 数组 ，用于标记目标字符串 的每个位置是否已经被覆盖。
- 数组 ，用于存储答案。
接下来，我们进行拓扑排序。在拓扑排序的每一步中，我们取出队首的窗口编号 ，并将 放入答案数组 中。然后，我们枚举字母印章中的每个位置 ，如果第 个窗口中的第 个位置未被覆盖，那么我们就将其覆盖，并将 数组中所有与第 个窗口中的第 个位置相同的窗口的入度减少 。如果某个窗口的入度变为 ，那么我们就将其放入队列 中等待下一次处理。
在拓扑排序结束后，如果目标字符串 的每个位置都被覆盖，那么答案数组 中存储的就是我们要求的答案。否则，目标字符串 无法被覆盖，我们就返回一个空数组。
时间复杂度 ，空间复杂度 。其中 和 分别是目标字符串 和字母印章的长度。
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 []
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N(N-M)) |
| 空间 | O(N(N-M)) |
面试官常问的追问
外企场景- question_mark
Look for understanding of stack-based state management and its application in string transformations.
- question_mark
Check how the candidate handles efficient operations under constraints, particularly with greedy strategies.
- question_mark
Evaluate the candidate’s approach to managing the state of transformations and ensuring correct sequence tracking.
常见陷阱
外企场景- error
Failure to efficiently manage the transformation state could lead to exceeding the operation limits.
- error
Incorrect placement of the stamp could result in an incomplete or incorrect transformation.
- error
Not using the stack to track operations properly could lead to missing valid solutions or incorrect sequencing.
进阶变体
外企场景- arrow_right_alt
Different constraints on the number of stamp operations, making the solution more challenging in terms of efficiency.
- arrow_right_alt
Allowing multiple stamps to overlap, requiring a more complex state management strategy.
- arrow_right_alt
Providing a scenario where the stamp is shorter than the target, emphasizing optimization of operations.