05 August 2008
戳印序列
你想要用小写字母组成一个目标字符串 target。
开始的时候，序列由 target.length 个 ’?’ 记号组成。而你有一个小写字母印章 stamp。
在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行 10 * target.length 个回合。
举个例子，如果初始序列为 “?????”，而你的印章 stamp 是 ”abc”，那么在第一回合，你可以得到 ”abc??”、”?abc?”、”??abc”。（请注意，印章必须完全包含在序列的边界内才能盖下去。）
如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。
例如，如果序列是 “ababc”，印章是 “abc”，那么我们就可以返回与操作 ”?????” -> “abc??” -> “ababc” 相对应的答案 [0, 2]；
另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成。任何超过此数字的答案将不被接受。
1
2
3
输入：stamp = "abc", target = "ababc"
输出：[0,2]
（[1,0,2] 以及其他一些可能的结果也将作为答案被接受）
我们对每个窗口维护两个集合 made 和 todo，前者表示和 stamp 可以匹配的位置，后者表示不可以匹配的位置（后者中只有某个位置的字符变成了问号，它才会变成可以匹配的位置）。只有当一个窗口的 todo 集合为空，这个窗口才可以被戳印，从而把一些字符变成问号。
我们用一个队列存储所有因为戳印而变成问号的字符位置。队列初始时包含所有 todo 集合一开始就为空的窗口对应的位置。当我们取出队列中的一个位置时，我们遍历所有覆盖了该位置的窗口，并且更新这些窗口的 todo 集合。如果 todo 集合变为空，那就说明产生了一个新的可被戳印的窗口，我们把这个窗口中所有未变成问号的字符的位置添加入队列中。
O(N(N−M))，其中 M 和 N 分别是数组 stamp 和 target 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public int[] movesToStamp(String stamp, String target) {
int M = stamp.length(), N = target.length();
Queue<Integer> queue = new ArrayDeque();
boolean[] done = new boolean[N];
Stack<Integer> ans = new Stack();
List<Node> A = new ArrayList();
for (int i = 0; i <= N - M; ++i) {
// For each window [i, i+M), A[i] will contain
// info on what needs to change before we can
// reverse stamp at this window.
Set<Integer> made = new HashSet();
Set<Integer> todo = new HashSet();
for (int j = 0; j < M; ++j) {
if (target.charAt(i + j) == stamp.charAt(j))
made.add(i + j);
else
todo.add(i + j);
}
A.add(new Node(made, todo));
// If we can reverse stamp at i immediately,
// enqueue letters from this window.
if (todo.isEmpty()) {
ans.push(i);
for (int j = i; j < i + M; ++j)
if (!done[j]) {
queue.add(j);
done[j] = true;
}
}
}
// For each enqueued letter (position),
while (!queue.isEmpty()) {
int i = queue.poll();
// For each window that is potentially affected,
// j: start of window
for (int j = Math.max(0, i - M + 1); j <= Math.min(N - M, i); ++j) {
if (A.get(j).todo.contains(i)) { // This window is affected
A.get(j).todo.remove(i);
if (A.get(j).todo.isEmpty()) {
ans.push(j);
for (int m : A.get(j).made)
if (!done[m]) {
queue.add(m);
done[m] = true;
}
}
}
}
}
for (boolean b : done)
if (!b) return new int[0];
int[] ret = new int[ans.size()];
int t = 0;
while (!ans.isEmpty())
ret[t++] = ans.pop();
return ret;
}
}
class Node {
Set<Integer> made, todo;
Node(Set<Integer> m, Set<Integer> t) {
made = m;
todo = t;
}
}