87.py

'''
 Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

 Below is one possible representation of s1 = "great":

 great
 / \
 gr eat
 / \ / \
 g r e at
 / \
 a t

 To scramble the string, we may choose any non-leaf node and swap its two children.

 For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

 rgeat
 / \
 rg eat
 / \ / \
 r g e at
 / \
 a t

 We say that "rgeat" is a scrambled string of "great".
'''

classSolution(object):
def__init__(self):
self.cache= {}

defisScramble(self, s1, s2):
ifs1==s2:
returnTrue
ifs1+s2inself.cache:
returnself.cache[s1+s2]
iflen(s1) !=len(s2) orsorted(s1) !=sorted(s2):
self.cache[s1+s2] =False
returnFalse
forindexinrange(1, len(s1)):
ifself.isScramble(s1[:index], s2[:index]) andself.isScramble(s1[index:], s2[index:]):
self.cache[s1+s2] =True
returnTrue
ifself.isScramble(s1[:index], s2[-index:]) andself.isScramble(s1[index:], s2[0:-index]):
self.cache[s1+s2] =True
returnTrue

self.cache[s1+s2] =False
returnFalse