class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
}
};
936. 戳印序列
你想要用小写字母组成一个目标字符串 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 <= stamp.length <= target.length <= 1000stamp 和 target 只包含小写字母。原站题解
java 解法, 执行用时: 28 ms, 内存消耗: 42.7 MB, 提交时间: 2023-09-23 12:10:59
class Solution {
List<Integer> ans = new ArrayList<>();
public int[] movesToStamp(String stamp, String target) {
StringBuilder builder = new StringBuilder(target);
boolean flag = true;
int start = 0;
while (flag) {
flag = false;
//判断是否已经完成
if (done(builder, 0, builder.length())) {
return ans.stream().mapToInt(it -> it.intValue()).toArray();
}
//从头开始遍历所有位置
for (int i = start; i <= builder.length() - stamp.length(); i++) {
//假如从i开始这一段已经完成或者不能匹配，那么继续查找下一个位置
if (done(builder, i, i + stamp.length())) {
//从i开始这一段已经完成，下次可以从下一段开始查找
start = i + 1;
continue;
}
if (!compare(builder, stamp, i)) {
continue;
}
//将找到的这一段改成'?'
for (int j = 0; j < stamp.length(); j++) {
builder.setCharAt(i + j, '?');
}
flag = true;
//记下当前改变的这段的开始位置
ans.add(0, i);
break;
}
}
return new int[]{};
}
//判断builder中[start, start + stamp.length())是否符合要求
boolean compare(StringBuilder builder, String stamp, int start) {
for (int i = 0; i < stamp.length(); i++) {
if (builder.charAt(i + start) != stamp.charAt(i) && builder.charAt(i + start) != '?') {
return false;
}
}
return true;
}
//判断[start, end)这一段是否已经完成
boolean done(StringBuilder builder, int start, int end) {
for (int i = start; i < end; i++) {
if (builder.charAt(i) != '?') {
return false;
}
}
return true;
}
}
golang 解法, 执行用时: 20 ms, 内存消耗: 2.6 MB, 提交时间: 2023-09-23 12:10:43
func movesToStamp(stamp string, target string) []int {
bTarget := make([]byte, len(target))
bStamp := []byte(stamp)
for i := 0; i < len(target); i++ {
bTarget[i] = '?'
}
now := []byte(target)
ret := []int{}
var flag = true
for flag {
flag = false // 如果没有匹配到任何段，说明不能再匹配了，返回。
// 如果now中所有值都是‘？’，那么说明成功了，倒置ret，返回结果
if bytes.Compare(now, bTarget) == 0 {
for i := 0; i < len(ret)/2; i++ {
ret[i], ret[len(ret)-1-i] = ret[len(ret)-1-i], ret[i]
}
return ret
}
// 每次都从头开始匹配
for i := 0; i <= len(bTarget) - len(stamp); i++ {
// 如果这一段已经全部是‘？’，不需要再匹配
if bytes.Compare(bTarget[i:i+len(stamp)], now[i:i+len(stamp)]) == 0 {
continue
}
if compare(bStamp, now[i:i+len(stamp)]) {
ret = append(ret, i)
// 将所有值替换'?'
for j := i; j < i + len(stamp); j++ {
now[j] = '?'
}
flag = true
break
}
}
}
return []int{}
}
// 比较函数
func compare(bs, bt []byte) bool {
if bytes.Compare(bs, bt) == 0 {
return true
}
for i := 0; i < len(bs); i++ {
if bs[i] != bt[i] && bt[i] != '?' {
return false
}
}
return true
}
python3 解法, 执行用时: 148 ms, 内存消耗: 20 MB, 提交时间: 2023-09-23 12:10:34
class Solution:
def movesToStamp(self, stamp: str, target: str) -> List[int]:
M, N = len(stamp), len(target)
queue = collections.deque()
done = [False] * N
ans = []
A = []
for i in range(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 range(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 range(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 []
java 解法, 执行用时: 29 ms, 内存消耗: 47.9 MB, 提交时间: 2023-09-23 12:09:30
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;
}
}