0936-戳印序列

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

你想要用 小写字母 组成一个目标字符串 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 只包含小写字母。

方法一：逆推

分析

如果我们正着考虑戳印序列，即将问号序列变为目标序列 target，那么这个问题会很难下手，因为某一个戳印会将前面的戳印覆盖掉。但我们如果倒着考虑这个问题（逆推），即将目标序列 target 变为问号序列，那么这个问题就变得可解决了。

我们将 target 中从第 i 个字符开始的长度为 stamp.length 的字符串称为第 i 个窗口。在第一步时，只有和 stamp 完全匹配的窗口才能进行戳印，而被戳印的所有位置都会变成问号 ?，在后续的戳印过程中，问号可以匹配任意字符。

例如 target 为 "aabcaca" 且 stamp 为 "abca"，在逆推时，首先选择第 1 个窗口戳印，target 变为 "a????ca"，随后选择第 3，0 个窗口戳印，target 依次变为 "a??????"，"???????"。

算法

我们对每个窗口维护两个集合 made 和 todo，前者表示和 stamp 可以匹配的位置，后者表示不可以匹配的位置（后者中只有某个位置的字符变成了问号，它才会变成可以匹配的位置）。只有当一个窗口的 todo 集合为空，这个窗口才可以被戳印，从而把一些字符变成问号。

我们用一个队列存储所有因为戳印而变成问号的字符位置。队列初始时包含所有 todo 集合一开始就为空的窗口对应的位置。当我们取出队列中的一个位置时，我们遍历所有覆盖了该位置的窗口，并且更新这些窗口的 todo 集合。如果 todo 集合变为空，那就说明产生了一个新的可被戳印的窗口，我们把这个窗口中所有未变成问号的字符的位置添加入队列中。

[sol1]
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
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;
    }
}
[sol1]
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
class Solution(object):
    def movesToStamp(self, stamp, target):
        M, N = len(stamp), len(target)

        queue = collections.deque()
        done = [False] * N
        ans = []
        A = []
        for i in xrange(N - M + 1):
            # For each window [i, i+M),
            # A[i] will contain info on what needs to change
            # before we can reverse stamp at i.

            made, todo = set(), set()
            for j, c in enumerate(stamp):
                a = target[i+j]
                if a == c:
                    made.add(i+j)
                else:
                    todo.add(i+j)
            A.append((made, todo))

            # If we can reverse stamp at i immediately,
            # enqueue letters from this window.
            if not todo:
                ans.append(i)
                for j in xrange(i, i + len(stamp)):
                    if not done[j]:
                        queue.append(j)
                        done[j] = True

        # For each enqueued letter,
        while queue:
            i = queue.popleft()

            # For each window that is potentially affected,
            # j: start of window
            for j in xrange(max(0, i-M+1), min(N-M, i)+1):
                if i in A[j][1]:  # This window is affected
                    A[j][1].discard(i) # Remove it from todo list of this window
                    if not A[j][1]:  # Todo list of this window is empty
                        ans.append(j)
                        for m in A[j][0]: # For each letter to potentially enqueue,
                            if not done[m]:
                                queue.append(m)
                                done[m] = True

        return ans[::-1] if all(done) else []

复杂度分析

  • 时间复杂度：O(N(N-M))，其中 M 和 N 分别是数组 stamp 和 target 的长度。

  • 空间复杂度：O(N(N-M))。

 Comments
On this page
0936-戳印序列