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
My code:
import operator
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
label=self.subScramble(s1, s2, 0, len(s1)-1, 0, len(s2)-1)
#First buildtree
#list1=[]
#self.Build_tree(s1,0,len(s1),list1)
#list2=[]
#self.Build_tree(s2,0,len(s2),list2)
#print(list1)
#print(list2)
#if len(list1)!=len(list2):
# return False
#set2=set(list2)
#label=bool(operator.eq(list1,list2))
return label
def subScramble(self, s1, s2, a1, a2, b1, b2):
if a2-a1 != b2-b1:
return False
if a1 == a2:
return s1[a1] == s2[b1]
if sorted(s1[a1:a2+1]) != sorted(s2[b1:b2+1]):
return False
for i in range(a1, a2):
if self.subScramble(s1, s2, a1, i, b1, b1+i-a1) and self.subScramble(s1, s2, i+1, a2, b2-a2+i+1, b2):
return True
if self.subScramble(s1, s2, a1, i, b2-i+a1, b2) and self.subScramble(s1, s2, i+1, a2, b1, b1+a2-i-1):
return True
return False
def Build_tree(self,s,i,j,list1):
if j-i==0:
return
if j-i==1:
list1.append(s[i])
return
if j-i==2:
if s[i]<s[i+1]:
list1.append([s[i],s[i+1]])
else:
list1.append([s[i+1],s[i]])
return
mid=int((i+j)/2)
self.Build_tree(s,i,mid,list1)
self.Build_tree(s,mid,j,list1)