题目：
使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。
给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。
基本思路：
本题有点二叉树的感觉，这里可以想象每个字符在二叉树的叶子节点，然后左右叶子可以随意扭动而等效。
但是上面的理解没有帮到我解题，说明还是不够深刻。
没办法，只能暴力遍历递归寻找了。
这里递归的思路是根据，
判断一个字符串是否可能是另一个扰乱得到，那么首先它们内字符的种类和数目是一致的。否则就没有可能
我们这里为了表达方便，把扰乱中的交换称为旋转操作，旋转的中心位置称为旋转点(不旋转的话则统一称为分割点，即旋转点也是分割点，但是会做旋转操作)。一个字符串可以由另一个扰乱获得，称它们之间存在关系(匹配)。
于是最暴力的方法就是，
1.逐个字符的遍历字符串，寻找可能分割的点， 需要满足分割点左侧或者右侧的各个字符数目与目标字符对应位置的字符种类和数目一致(如果旋转的话则需要颠倒一下s2)
2.剩下找到的分割点点左侧和右侧子字符串间是否存在关系，这个就交给递归去做。
但是这样发现字符串一长，这个算法就太慢了，甚至可能会dead。
所以我们只能去优化递归，减少无效或者重复的递归。
递归优化：
我们是按照顺序递归的，这里如果我找到某个分割点，其满足了旋转或者不旋转对应左右侧都匹配，那么就会结束递归返回True，
所以当我遍历到某个点的时候，前面所有的点，都不能让该点左右侧均匹配上。
但是按照暴力递归，我们还是要再重复判断一遍，这里就会发现有些判断是之前已经做过了，可以直接省略不做的。
直观的：
如果我们按照顺序对s1从左到右寻找，如果某个点满足了基本条件，
比如其左侧字符的种类或数目与s2的左侧一致，
那么我们可以推断，要使得当前点可以作为分割点使得s1和s2(先考虑在该点不旋转)匹配上的话，那么该点左侧的子字符串必须通过在内部分割点上旋转匹配上。
这里听着很拗口，看下面图就好理解了：
这里跑到Now位置发现s1,s2左侧字符串字符种类和数目一致，
如果Now是我们最终要找的分割点，即s1,s2可以通过Now匹配上(他们关于Now左右侧子字符串都匹配上)，那么Now左侧的子字符串肯定不能通过某个分割点非旋转的匹配。
我们使用反证法，如果存在一个分割点Fail在当前Now的左侧，且满足Fail左侧的s1和s2子字符串匹配，右侧(Fail--Now之间)子字符串也匹配。
那么我们可以看到，当我们在之前遍历到Fail的时候，Fail左侧肯定匹配上了，Fail右侧，如果以Now为分隔点，不旋转的话，Now左侧(Fail--Now之间)肯定匹配上了，Now右侧也匹配上了。
那么Fail点就已经满足要求。
这就说明我们在判断Now点(非旋转分割点)左侧的时候，只需要再考虑旋转的分割点即可，不必再考虑非旋转的分割点。
同理，我们在从左到右判断旋转分割点的时候，递归判断其左侧，只需要考虑非旋转分割点即可，不必再重复考虑旋转分割点了。
但是右侧没有遍历到，所以还是都要考虑的。
所以代码实现的时候，我们将遍历旋转分割点和非旋转分割点作为两个函数处理。
另外这里判断两个字符串内部字符数目和种类一致，使用了一个自定义的字典结构，这个可能比较费时。也可以尝试其他数据结构。
代码实现：
[Python] 纯文本查看 复制代码 class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
if len(s1)!=len(s2):
return False
DIC1 = self.CharCnt(s1)
DIC2 = self.CharCnt(s2)
if DIC1!= DIC2:return False
return self.SwitchJudge(s1,s2)
def SwitchJudge(self,s1,s2):
if s1==s2:return True
if len(s1)<4 and self.CharCnt(s1)==self.CharCnt(s2):return True
if self.JudgeRight(s1,s2) or self.JudgeLeft(s1,s2):
return True
return False
def JudgeRight(self,s1,s2):
if s1==s2:return True
if len(s1)<4 and self.CharCnt(s1)==self.CharCnt(s2):return True
Dic0 = {}
Dic2_t = {}
for i in range(len(s1)-1):
if s1[i] in Dic0:
Dic0[s1[i]]+=1
else:
Dic0[s1[i]]=1
if s2[-(i + 1)] in Dic2_t:
Dic2_t[s2[-(i + 1)]] += 1
else:
Dic2_t[s2[-(i + 1)]] = 1
## judge
if Dic0 == Dic2_t:
# print('head', s1[:i + 1], s2[:i + 1], s1[i + 1:], s2[i + 1:])
j1 = self.JudgeLeft(s1[:i+1],s2[-(i+1):])
j2 = self.SwitchJudge(s1[i+1:],s2[:-(i+1)])
if j1 and j2:
return True
return False
def JudgeLeft(self, s1, s2):
if s1 == s2: return True
if len(s1) < 4 and self.CharCnt(s1)==self.CharCnt(s2): return True
Dic0 = {}
Dic2_h = {}
for i in range(len(s1) - 1):
if s1[i] in Dic0:
Dic0[s1[i]] += 1
else:
Dic0[s1[i]] = 1
if s2[i] in Dic2_h:
Dic2_h[s2[i]] += 1
else:
Dic2_h[s2[i]] = 1
## judge
if Dic0 == Dic2_h:
# print('tail',s1[:i+1],s2[-(i+1):],s1[i+1:],s2[:-(i+1)])
j1 = self.JudgeRight(s1[:i+1],s2[:(i+1)])
j2 = self.SwitchJudge(s1[i+1:],s2[(i+1):])
if j1 and j2:
return True
return False
def CharCnt(self,LST):
Dic = {}
for a in LST:
if a in Dic:
Dic[a]+=1
else:
Dic[a]=1
return Dic
最终结果：
总结：
数据结构还不够娴熟，堪堪跑过。 | 
发表于 2021-11-25 12:18
