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;

    }
}