87. 扰乱字符串
递归：
我们用dg(i,j,length)表示s1[i:i+length]与s2[j:j+length]是否为扰乱字符串。
递归的终止条件：
显然如果s1[i:i+length]与s2[j:j+length]相等，dg(i,j,length)返回True
如果s1[i:i+length]与s2[j:j+length]中的元素不相同，dg(i,j,length)返回False
递归过程：
如果s1[i:i+length]与s2[j:j+length]是扰乱字符串，那么就是说，至少存在一个k，k的取值范围从1到length-1，使得(dg(i+k,j+k,length-k) and dg(i,j,k)) or (dg(i,j+length-k,k) and dg(i+k,j,length-k))为True。
如果我们遍历所有的k，(dg(i+k,j+k,length-k) and dg(i,j,k)) or (dg(i,j+length-k,k) and dg(i+k,j,length-k))都是False，那么说明s1[i:i+length]与s2[j:j+length]不是扰乱字符串。
代码：
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
len1 = len(s1)
if len1!=len(s2):
return False
def dg(i,j,length):
if s1[i:i+length]==s2[j:j+length]:
return True
if sorted(s1[i:i+length])!=sorted(s2[j:j+length]):
return False
for k in range(1,length):
if (dg(i+k,j+k,length-k) and dg(i,j,k)) or (dg(i,j+length-k,k) and dg(i+k,j,length-k)):
return True
return False
return dg(0,0,len1)
关键词：递归
