leetcode: 87. Scramble String

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

class Solution():
    def isScramble(self, s1, s2):
        if len(s1)!=len(s2) or set(s1)!=set(s2):
            return False
        if s1==s2:
            return True
        if not s1 and not s2:
            return True
        return self.recurse(s1, s2) or self.recurse(s1, s2[::-1])

    def recurse(self, s1, s2):
        from collections import defaultdict
        d = defaultdict(int)
        breakpoints = []
        for i, c in enumerate(s1[:-1]):
            d[c]+=1
            c2 = s2[i]
            d[c2]-=1
            same = True
            for cc in d:
                if d[cc]!=0:
                    same=False
                    break
            if same:
                breakpoints.append(i)
        for b in breakpoints:
            if self.isScramble(s1[:b+1], s2[:b+1]) and self.isScramble(s1[b+1:], s2[b+1:]):
                return True
        return False


if __name__ == "__main__":
    assert Solution().isScramble("rgtae", "great") == True