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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

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.maps = {}

	def isScramble(self, 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):
		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):

		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 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)