class Solution:

# @return a boolean

def **init**(self):

self.cache = {}

```
def isScramble(self, s1, s2):
if (s1, s2) in self.cache:
return self.cache[(s1, s2)]
if len(s1) == 1:
self.cache[(s1,s2)] = (s1 == s2)
return self.cache[(s1,s2)]
length = len(s2)
for i in range(1, length): #split point 1~len(s2)-1
if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])) \
or (self.isScramble(s1[length-i:], s2[:i]) and self.isScramble(s1[:length-i], s2[i:])):
self.cache[(s1,s2)] = True
return True
self.cache[(s1,s2)] = False
return False
```

I used Memoization DP. But I don't know if this solution is good enough. I think the time complexity is exponential as O(4^(length of string)), is it?

Any way to improve this solution?