遞歸的方法
class Solution:
# @return a boolean
def isScramble(self, s1, s2):
if len(s1)!=len(s2):
return False
if s1==s2:
return True
'''
l1=list(s1)
l2=list(s2)
l1.sort()
l2.sort()
if l1!=l2:
return False
'''
zd1={};zd2={}
for s in s1:
if s not in zd1:
zd1[s] = 1
else:
zd1[s] += 1
for s in s2:
if s not in zd2:
zd2[s] = 1
else:
zd2[s] += 1
if zd1 != zd2:
return False
length=len(s1)
for i in range(1,length):
if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]):
return True
if self.isScramble(s1[:i],s2[length-i:]) and self.isScramble(s1[i:],s2[:length-i]):
return True
return False
