936. 戳印序列

Problem: 936. 戳印序列

思路

这道题目要求我们通过使用印章来印刷目标字符串，使得目标字符串最终变成全为’?‘的字符串。我们可以使用贪心的思想来解决这个问题。
首先，我们需要找到所有可以匹配印章的位置，即目标字符串中与印章的第一个字符相同的位置。然后，我们可以尝试在这些位置上使用印章进行印刷，如果印章的字符与目标字符串的对应位置字符相同，我们可以将该位置的字符替换为’?‘，表示已经印刷过。然后，我们继续寻找下一个可以匹配印章的位置，重复上述步骤，直到无法找到可以匹配印章的位置为止。
最后，我们需要检查目标字符串是否已经全部变为’?'，如果是，则返回印刷的顺序，否则返回空数组。

解题方法

将印章和目标字符串转换为字符数组，方便操作。
初始化一个数组indegree，用于记录每个可以匹配印章的位置的入度，初始值为印章的长度。
建立一个图，用于记录每个位置与其他可以匹配印章的位置的关系。图的每个节点表示目标字符串的位置，节点之间的边表示可以匹配印章的关系。
初始化一个队列queue，用于存储可以匹配印章的位置。
遍历目标字符串，找到所有可以匹配印章的位置，并更新indegree和queue。
初始化一个布尔数组visited，用于记录每个位置是否已经访问过。
初始化一个数组path，用于存储印刷的顺序。
使用广度优先搜索（BFS）遍历图，将印刷的顺序存储在path中。
检查path的长度是否等于目标字符串长度减去印章长度加一，如果是，则将path逆序调整，并返回path，否则返回空数组。

复杂度

时间复杂度:

时间复杂度: $O(n^2)$，其中n为目标字符串的长度。建立图的时间复杂度为$O(n^2)$，BFS的时间复杂度为$O(n^2)$。

空间复杂度:

空间复杂度: $O(n)$，其中n为目标字符串的长度。需要使用额外的空间存储图、队列、布尔数组和印刷顺序数组。

Code

class Solution {public int[] movesToStamp(String stamp, String target) {char[] s = stamp.toCharArray();char[] t = target.toCharArray();int m = s.length;int n = t.length; int[] indegree = new int[n - m + 1];Arrays.fill(indegree, m);// 建图List<List<Integer>> graph = new ArrayList<>();for(int i = 0; i < n; i++) {graph.add(new ArrayList<>());}int[] queue = new int[n - m + 1];int l = 0, r = 0;for(int i = 0; i < n - m + 1; i++) {for(int j = 0; j < m; j++) {if(t[i + j] == s[j]) {if(--indegree[i] == 0) {queue[r++] = i;}} else {graph.get(i + j).add(i);}}}// 同一个位置看上的错误 不要重复统计boolean[] visited = new boolean[n];int[] path = new int[n - m + 1];int size = 0;while(l < r) {int cur = queue[l++];path[size++] = cur;for(int i = 0; i < m; i++) {if(!visited[cur + i]) {visited[cur + i] = true;for(int next : graph.get(cur + i)) {if(--indegree[next] == 0) {queue[r++] = next;}}}}}if (size != n - m + 1) {return new int[0];}// path逆序调整for (int i = 0, j = size - 1; i < j; i++, j--) {int tmp = path[i];path[i] = path[j];path[j] = tmp;}return path;}
}