你想要用小写字母组成一个目标字符串 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 <= 1000
- stamp 和 target 只包含小写字母。
本身没做出来，看的答案和discuss里的提示才想到这个方法
思路分析：
假设我们经过若干次操作使得stamp变为target，那么在最后一次操作中，一定使得target某处位置变成了stamp。
故条件1：if stamp not in target: return []
我们采取反向还原的方法来判断，例如stamp = 'abca', target = 'aabcaca'
在target中找到一个’abca’，target 变为 a????ca
如何继续找下一个和stamp匹配的字段呢？
因为’?’在最后一次会被覆盖，所以?之前是什么我们可以随便定，那么在这里，??ca与’abca’也匹配，’a???’与’abca’也匹配。
重复进行该操作，直至target被完全还原，或没法还原1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution(object):
# 判断是否匹配
def check(self, s, t):
for i in range(len(s)):
if t[i] == '?': continue
if s[i] != t[i]: return False
return True
def movesToStamp(self, s, target):
turn = 0 # 匹配轮次，不超过10*len(target)
n, m = len(s), len(target)
res = []
compare = '?' * n
while turn < 10*m:
tmp = turn
for i in range(m-n+1):
if target[i:i+n] != compare and self.check(s, target[i:i+n]):
turn = turn + 1
res.append(i)
target = target[:i] + compare + target[i+n:]
# 成功还原，反向返回res
if target == '?'*m: return res[::-1]
# 如果一个匹配的都没找到，说明无法还原了，直接break
if turn == tmp: break
return []