[2ND TRY]
Version #3 Greedy without any reason
class Solution {
private int matchedCount;
public int[] movesToStamp(String stamp, String target) {
char[] chars = target.toCharArray();
matchedCount = 0;
List<Integer> result =new LinkedList<>();
while(matchedCount != target.length()) {
if (!match(stamp, target, chars, result)) break;
}
return matchedCount == target.length() ? result.stream().mapToInt(a -> a).toArray() : new int[0];
}
private boolean match(String stamp, String target, char[] chars, List<Integer> result) {
for (int i = 0; i <= target.length() - stamp.length(); i++) {
int j = 0;
boolean canMatch = false;
for (j = 0; j < stamp.length(); j++) {
if (chars[i + j] == stamp.charAt(j)) {
canMatch = true;
} else if (chars[i + j] != '?') {
break;
}
}
if (canMatch && j == stamp.length()) {
for (j = 0; j < stamp.length(); j++) {
if (chars[i + j] != '?') {
chars[i + j] = '?';
matchedCount++;
}
}
result.add(0, i);
return true;
}
}
return false;
}
}
Version #2 TLE BFS
public int[] movesToStamp(String stamp, String target) {
String mask = "";
String result = "";
int stampLen = stamp.length();
for (int i = 0; i < stampLen; i++) mask += "?";
for (int i = 0; i < target.length(); i++) result += "?";
// key-string after stamped like ababc -> ab???, value-list of indexed where we have put stamps
Map<String, List<Integer>> map = new HashMap<>();
// string[0] places we can still put stamp, string[1] target
Queue<String> que =new LinkedList<>();
que.offer(target);
int step = 0;
while (!que.isEmpty()) {
step++;
if (step > 10) return new int[0];
int size = que.size();
while (size-- > 0) {
String curr = que.poll();
List<Integer> stamped = map.getOrDefault(curr, new ArrayList<>());
// ab???, [2]
for (int i = 0; i <= target.length() - stampLen; i++) {
if (stamped.contains(i)) continue; // skip if we have already stamped on this position
int j = 0;
boolean valid = false;
for (j = 0; j < stampLen; j++) {
if (stamp.charAt(j) == target.charAt(i + j)) {
valid = true; // this stamp contributes to our result
} else if (curr.charAt(i + j) != '?') {
break;
}
}
if (valid && j == stampLen) { // we can stamp here
String next = curr.substring(0, i) + mask + curr.substring(i + stampLen);
List<Integer> nextStamped = new LinkedList<>(stamped);
nextStamped.add(0, i);
if (next.equals(result)) return nextStamped.stream().mapToInt(a -> a).toArray();
if (!map.containsKey(next)) {
map.put(next, nextStamped);
que.offer(next);
}
}
}
}
}
return new int[0];
}
[1ST TRY]
一个非常有意思的题
怎么说，中心思想感觉上非常像topological sort
用一个stamp的start index来表示 distinct stamp
一开始默认为targe从0 一直到 targetLen - stampLen 都会有潜在的stamp可以盖章
我们希望当一个stamp落下的时候，它的所有character都和target是matched
所以当我们用 O(targetLen*stampLen)搜索整个target，找到所有character完全match的stamp，就可以把它们放入我们的done queue里面，代表这些位置是可以盖章的
那么盖章以后的效果是什么呢，就是使盖章的char完全满足target, 并且覆盖之前不满足的任何char
stamp = "abca", target = "aabcaca"// stamp a b c a
// target a a b c a c a
// matched todo
// 0 -> 0 1 2 3
// 1 -> 1 2 3 4
// 2 -> 2 3 4 5
// 3 -> 3 4 5 6
// use index i to represent where to put stamp
譬如当我们在 index=2盖章后，就完全使整个[index, index + stampLen) 满足条件
整个区域都可以在boolean[] visited 里面设为true
我们找哪些 stamp 的todo list里面有这些点，就可以把他们移除掉，因为后面的stamp 帮助他们完成了这些点
如果这些候选的stamp 的todo list 空了，有两种情况
重点！！！
1. 虽然它的todo list空了，但是它有些点是自己的matched点，也就是说需要盖下这个章才能满足
2.其他的stamp帮它完成了它的任务，在他的范围内所有char都已经盖完了，那么这个stamp就不需要盖章了
具体是1还是2，要在我们位于stamp的时候扫一遍它的范围，看看有没有visited[p] == false
如果有的话，要push到done里面去等待该站，如果没有就完全不用管了
while停止的条件是done的list全部pop完，也就是说该盖的章全都盖上
这里有个bug就是下面这种情况
最后能盖的章都盖完了，还有很多没有解决的点，证明没有可行解，要返回new int[0]
"mda" "mdadddaaaa"时间复杂度大约是 O(MN) 的量级
class Solution {
public int[] movesToStamp(String stamp, String target) {
Deque<Integer> result = new ArrayDeque<>();
int stampLen = stamp.length();
int targetLen = target.length();
Map<Integer, Set<Integer>> todo = new HashMap<>();
Queue<Integer> done = new LinkedList<>();
for (int i = 0; i <= targetLen - stampLen; i++) {
Set<Integer> todoIndex = new HashSet<>();
for (int j = 0; j < stampLen; j++) {
if (stamp.charAt(j) != target.charAt(i + j)) {
todoIndex.add(i + j);
}
}
if (todoIndex.isEmpty()) {
done.offer(i);
} else {
todo.put(i, todoIndex);
}
}
boolean[] visited = new boolean[targetLen];
while (!done.isEmpty()) {
// p + stampLen = i
// p = i - stampLen + 1
// i (i+stampLen)
// abca
// aabcaca
int curr = done.poll();
result.addFirst(curr);
// System.out.println("curr -> " + curr);
for (int changedPos = curr; changedPos < curr + stampLen; changedPos++) {
visited[changedPos] = true;
// check all stamp that might contain changedPos
for (int stampIndex = Math.max(0, curr - stampLen + 1); stampIndex < Math.min(curr + stampLen, targetLen); stampIndex++) {
Set<Integer> todoIndex = null;
if ((todoIndex = todo.get(stampIndex)) != null) {
if (todoIndex.contains(changedPos)) {
todoIndex.remove(changedPos);
if (todoIndex.size() == 0) {
todo.remove(stampIndex);
for (int p = 0; p < stampLen; p++) {
if (!visited[stampIndex + p]) {
done.offer(stampIndex);
break;
}
}
}
}
}
}
}
}
for (boolean visit : visited) {
if (!visit) {
return new int[0];
}
}
return result.stream().mapToInt(i -> i).toArray();
}
}
No comments:
Post a Comment