题意
见题目链接
解答
因为二叉树是由字符串递归地分割生成的，所以能很自然地想到递归的解法。遍历 s1 的所有可能的分割点，每次分割得到两个非空子字符串 s1_left 和 s1_right，同时对 s2 做同样操作得到 s2_left 和 s2_right，注意到 s2 的左边和右边可能经过“扰乱”操作，所以 s2 有两种分割方式：1. s1_left 与 s2_left 长度相等，2. s1_left 与 s2_right 长度相等。然后判断 s1 和 s2 的子字符串是否能由“扰乱”操作得到。代码实现如下：
递归版本
class Solution:
def isScramble(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if len(s1) != len(s2):
return False
if len(s1) == 1:
if s1[0] == s2[0]:
return True
else:
return False
for l in range(1,len(s1)):
part11 = s1[:l]
part12 = s1[l:]
part21 = s2[:l]
part22 = s2[l:]
part31 = s2[-l:]
part32 = s2[:-l]
if self.isScramble(part11,part21) and self.isScramble(part12,part22):
return True
if self.isScramble(part11,part31) and self.isScramble(part12,part32):
return True
return False
但是提交后运行结果是超时:确实，有许多子字符串对被重复求解，类似于递归求斐波那契数列。
斐波那契数列中，我们是用数组保存之前计算得到的结果，这样就能保证每个子问题只被求解一次。那在本题中，能否也将子问题的结果保存起来呢？
[解释部分待完成]
迭代版本
class Solution:
def isScramble(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if len(s1) != len(s2):
return False
store = [[[False]*(len(s1)+1) for i in range(len(s1))] for j in range(len(s1))]
for i in range(len(s1)):
for j in range(len(s1)):
if s1[i] == s2[j]:
store[i][j][1] = True
for length in range(1,len(s1)+1):
for start1 in range(len(s1)-(length-1)):
for start2 in range(len(s1)-(length-1)):
for l in range(1,length):
if store[start1][start2][l] and store[start1+l][start2+l][length-l]:
store[start1][start2][length] = True
if store[start1][start2+length-l][l] and store[start1+l][start2][length-l]:
store[start1][start2][length] = True
return store[0][0][len(s1)]
