这个题解采用了回溯的思路。从目标字符串的左端开始，先找到与印章开头相同的部分，然后递归地寻找右边剩余部分的合法分割。如果找不到，就回溯尝试更短的开头。当找到一个与印章完全相同的子串时，转而从右端开始寻找与印章结尾相同的部分，直到找到一个完整的合法分割。在回溯的过程中，用一个集合记录所有不能完成的开头坐标，避免重复搜索。
时间复杂度: O(m^(n/m))
空间复杂度: O(n^2/m)
class Solution:
def movesToStamp(self, stamp, target):
self.invalid = set() #所有不能完成的开头坐标
return self.recurtion(stamp, target, 0)
def recurtion(self, stamp, target, idx):
ans = []
n = len(stamp)
while True:
l = self.left(target, idx, stamp)
if l == 0:
return []
if l == n: #找到全部的stamp，转而寻找结尾相同
break
for i in range(1, l):
if idx + i not in self.invalid: #最长的开头可能反而不符合条件，遍历所有可能的短开头
tmp = self.recurtion(stamp, target, idx + i)
if tmp:
return ans + [idx] + tmp
else:
self.invalid.add(idx + i)
ans.append(idx)
idx += l
idx2 = idx + l
rl = []
while True:
if idx2 == len(target): #右端点同时是结尾相同部分的末尾，找到和符合要求的方法
return ans + rl[::-1] + [idx]
if idx2 not in self.invalid: #检验该右端点(包含全部stamp)后面是否可以作为左端点找到合法分割
tmp = self.recurtion(stamp, target, idx2)
if tmp:
return ans + rl[::-1] + [idx] + tmp
else:
self.invalid.add(idx2)
r = self.right(target, idx2, stamp)
if r == 0:
idx0, tmp = self.check(target, idx2, stamp)
if tmp:
return [idx0] + ans + rl[::-1] + [idx] + tmp
return []
rl.append(idx2 + r - n)
idx2 += r
return ans
def left(self, t, idx, s): #寻找开头与stamp相同的部分
i = 1
while i <= len(s) and t[idx: idx + i] == s[:i]:
i += 1
return i - 1
def right(self, t, idx, s):
for l in range(1, len(s)):
if t[idx: idx + l] == s[-l:]:
return l
return 0
#当前是结尾优于当前是开头(不能接结尾)，开头->结尾须要一个完整的stamp
def check(self, t, idx, s):
l = 1
while idx + l < len(t) and l < len(s) - 1:
if t[idx + l] == s[0]:
i = 0
while i + l < len(s):
if t[idx: idx + l] == s[i: i + l]:
break
i += 1
if i + l < len(s) and idx + l not in self.invalid:
tmp = self.recurtion(s, t, idx + l)
if tmp:
return idx - i, tmp
else:
self.invalid.add(idx + l)
l += 1
return -1, []