#NEWLINE# def isScramble( self , s1 , s2 ) : #NEWLINE# #INDENT# "\n        dfs\n        partition and compare\n\n        Compare two trees constructed from the two strings respectively. Two trees are scramble of the other iff A's\n        left/right subtree is the scramble of B's left/right subtree or A's left/right subtree is the scramble of B's\n        right/left subtree.\n\n        .....|... vs. .....|... or\n        ...|..... vs. .....|...\n\n        :param s1:\n        :param s2:\n        :return: boolean\n        " #NEWLINE# if ( len ( s1 ) != len ( s2 ) ) : #NEWLINE# #INDENT# return False #NEWLINE# #UNINDENT# chars = [ 0 for _ in xrange ( 26 ) ] #NEWLINE# for char in s1 : #NEWLINE# #INDENT# chars [ ( ord ( char ) - ord ( 'a' ) ) ] += 1 #NEWLINE# #UNINDENT# for char in s2 : #NEWLINE# #INDENT# chars [ ( ord ( char ) - ord ( 'a' ) ) ] -= 1 #NEWLINE# #UNINDENT# for val in chars : #NEWLINE# #INDENT# if ( val != 0 ) : #NEWLINE# #INDENT# return False #NEWLINE# #UNINDENT# #UNINDENT# if ( len ( s1 ) == 1 ) : #NEWLINE# #INDENT# return True #NEWLINE# #UNINDENT# for i in xrange ( 1 , len ( s1 ) ) : #NEWLINE# #INDENT# 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 [ : ( len ( s2 ) - i ) ] ) ) ) : #NEWLINE# #INDENT# return True #NEWLINE# #UNINDENT# #UNINDENT# return False