0936：戳印序列（2583 分）

力扣第 109 场周赛第 4 题

题目

你想要用小写字母组成一个目标字符串 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. 1 <= stamp.length <= target.length <= 1000
2. stamp 和 target 只包含小写字母。

分析

• 显然最后一次印章必然和 stamp 完全匹配，考虑逆向推导
  • 先将 target 中和 stamp 完全匹配的子数组都替换为 ‘?’
  • 接着，假如 target 的某个子数组除了 ‘?’ 部分，都和 stamp 匹配，那么也都可以替换为 ‘?’
  • 依此类推，假如最后 target 都变成了 ‘?’，即代表成功
• 考虑如何实现
  • 将 target 所有长为 len(stamp) 的子数组看作节点
  • 子数组中和 stamp 不匹配的个数看作节点的度
  • 从度为 0 的节点 u 开始遍历
    • u 这个子数组覆盖的下标都变成 ‘?’
    • 遍历覆盖的每个下标 x
    • 假如其它某节点 v 覆盖了 x，且 x 贡献了 v 的度，那么 v 的度减 1
    • 如果 v 的度减为 0，即可作为下一轮遍历的节点
  • 这个过程非常类似拓扑排序，只是节点不直接相连，而是通过下标 x 的中介
  • 建图时，记录每个下标 x 产生贡献的节点列表即可
  • 注意下标 x 遍历后，要清除 x 的列表，因为贡献已减去了

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m,n = len(target),len(stamp)
        g = [[] for _ in range(m)]
        deg = [0]*(m-n+1)
        for u in range(m-n+1):
            for x in range(u,u+n):
                if target[x]!=stamp[x-u]:
                    g[x].append(u)
                    deg[u] += 1
        Q = deque([u for u in range(m-n+1) if deg[u]==0])
        res = []
        while Q:
            u = Q.popleft()
            res.append(u)
            for x in range(u,u+n):
                for v in g[x]:
                    deg[v] -= 1
                    if deg[v]==0:
                        Q.append(v)
                g[x].clear()
        return res[::-1] if all(a==0 for a in deg) else []

71 ms