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".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".


    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a


We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:


Input: s1 = "great", s2 = "rgeat"
Output: true


Example 2:


Input: s1 = "abcde", s2 = "caebd"
Output: false

Difficulty: interview

Starter code:

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        

Solutions:
class Solution:
     def isScramble(self, A, B):
         if len(A) != len(B) or sorted(A) != sorted(B):
             return False
 
         if len(A) == 1 or A == B:
             return True
 
         for i in range(1, len(A)):
             if self.isScramble(A[:i], B[:i]) and self.isScramble(A[i:], B[i:]):
                 return True
             elif self.isScramble(A[:i], B[-i:]) and self.isScramble(A[i:], B[:-i]):
                 return True
         return False

class Solution:
 
     def __init__(self):
         self._cache = {}
 
     def isScramble(self, A, B):
 
         if (A, B) in self._cache:
             return self._cache[(A, B)]
 
         if len(A) != len(B) or sorted(A) != sorted(B):
             self._cache[(A, B)] = False
             return False
 
         if len(A) == 1 or A == B:
             self._cache[(A, B)] = True
             return True
 
         for i in range(1, len(A)):
             if self.isScramble(A[:i], B[:i]) and self.isScramble(A[i:], B[i:]):
                 self._cache[(A, B)] = True
                 return True
             elif self.isScramble(A[:i], B[-i:]) and self.isScramble(A[i:], B[:-i]):
                 self._cache[(A, B)] = True
                 return True
         self._cache[(A, B)] = False
         return False

class Solution:
     def __init__(self):
         self.maps = {}
     
     def isScramble(self, s1, s2):
      #   print(s1, s2)
         if (s1,s2) in self.maps:
             return self.maps[(s1,s2)]
         if len(s1) != len(s2) or sorted(s1) != sorted(s2):
             self.maps[(s1,s2)] = False
             return False
         if s1 == s2:
             self.maps[(s1,s2)] = True
             return True
         n = len(s1)
         for sz in range(1,n):
             if ((self.isScramble(s1[:sz], s2[:sz]) and self.isScramble(s1[sz:], s2[sz:])) or
                (self.isScramble(s1[:sz], s2[-sz:]) and self.isScramble(s1[sz:], s2[:-sz]))):
                 self.maps[(s1,s2)] = True
                 return True
         self.maps[(s1,s2)] = False
         return False


class Solution:
     def isScramble(self, s1, s2):
         """
         :type s1: str
         :type s2: str
         :rtype: bool
         """
         if len(s1) != len(s2):
             return False
         if s1 == s2:
             return True
         if sorted(s1) != sorted(s2): # prunning
             return False
         for i in range(1, len(s1)):
             if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])) or \
             (self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i])):
                 return True
         return False

class Solution:
     d={}
     def isScramble(self, s1, s2):
         """
         :type s1: str
         :type s2: str
         :rtype: bool
         """
         if (s1,s2) in self.d:
             return self.d[(s1,s2)]
         if len(s1)!=len(s2) or sorted(s1)!=sorted(s2):
             return False
         if s1==s2:
             return True
         for i in range(len(s1)-1):
             if (self.isScramble(s1[:i+1],s2[:i+1]) and self.isScramble(s1[i+1:],s2[i+1:])) or \
                 (self.isScramble(s1[:i+1],s2[len(s1)-i-1:]) and self.isScramble(s1[i+1:],s2[:len(s1)-i-1])):
                 self.d[(s1,s2)]=True
                 return True
         self.d[(s1,s2)]=False
         return False


class Solution:
     def isScramble(self, s1, s2):
         if len(s1) != len(s2):
             return False
         if s1 == s2:
             return True
         if sorted(s1) != sorted(s2):
             return False
         for i in range(1,len(s1)):
             if (self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:])) or \
                     (self.isScramble(s1[:i],s2[-i:]) and self.isScramble(s1[i:], s2[:-i])):
                 return True
         return False

class Solution:
     def isScramble(self, s1, s2):
         """
         :type s1: str
         :type s2: str
         :rtype: bool
         """
         
         """
         CHECKING TWO STRINGS ARE ANAGRAMS IS FASTER BY SORTING THAN BY COUNTE (AT WHAT LEN DOES THIS FLIP)
         RETURNING WHEN SORTED(S1) != SORTED(S2[LEFT:RIGHT+1]) GOT MY CODE FROM 1800 MS TO 150MS.
         """
         
         def getfromdictt(strr, left, right):
             args = (strr, s2[left:right+1])
             if args in dictt:
                 return dictt[args]
             res = scramble(strr, left, right)
             dictt[args] = res
             return res
         
         def putindictt(strr, left, right, val):
             dictt[(strr, s2[left:right+1])] = val
             return val
         
         def scramble(s1, left, right):
             
             if sorted(s1) != sorted(s2[left:right+1]):
                 return putindictt(s1, left, right, False)
             # if collections.Counter(s1) != collections.Counter(s2[left:right+1]): return False
             
             
             if s2[left:right+1] == s1:
                 return putindictt(s1, left, right, True)
             
             for i in range(len(s1)-1):
                 leftstr, rightstr = s1[:i+1], s1[i+1:]
                 leftmatch = getfromdictt(leftstr, left, left+i)
                 rightmatch = getfromdictt(rightstr, left+i+1,right)
                 
                 if leftmatch and rightmatch:
                     return putindictt(s1, left, right, True)
                 
                 flipleftmatch = getfromdictt(rightstr, left, left + len(rightstr)-1)
                 fliprightmatch = getfromdictt(leftstr, left + len(rightstr), right)
 
                 if flipleftmatch and fliprightmatch:
                     return putindictt(s1, left, right, True)
             
             return putindictt(s1, left, right, False)
         
         dictt = {}
         return scramble(s1, 0, len(s1)-1)


class Solution:
     def isScramble(self, s1, s2):
         """
         :type s1: str
         :type s2: str
         :rtype: bool
         """
         if s1 == s2:
             return True
         if len(s1) != len(s2) or sorted(s1) != sorted(s2):
             return False
         dp = self.isScramble
         for i in range(1, len(s1)):
             for j in range(1, len(s2)):
                 if (dp(s1[:i], s2[:j]) and dp(s1[i:], s2[j:])) or (dp(s1[:i], s2[j:]) and dp(s1[i:], s2[:j])):
                     return True
         return False

class Solution:
     def isScramble(self, s1, s2):
         if sorted(s1) != sorted(s2): return False
         if len(s1) < 4 or s1 == s2: return True
         f = self.isScramble
         for i in range(1, len(s1)):
             if f(s1[:i], s2[:i]) and f(s1[i:], s2[i:]) or f(s1[:i], s2[-i:]) and f(s1[i:], s2[:len(s1) - i]):
                 return True
         return False


class Solution:
     def isScramble(self, s1, s2):
         """
         :type s1: str
         :type s2: str
         :rtype: bool
         """
         if len(s1)!=len(s2) or sorted(s1)!=sorted(s2):
             return False
         if s1==s2:
             return True
         for i in range(len(s1)-1):
             if (self.isScramble(s1[:i+1],s2[:i+1]) and self.isScramble(s1[i+1:],s2[i+1:])) or \
                 (self.isScramble(s1[:i+1],s2[len(s1)-i-1:]) and self.isScramble(s1[i+1:],s2[:len(s1)-i-1])):
                 return True
         return False