1
class Solution(object):
2
    def isScramble(self, s1, s2):
3
        """
4
        :type s1: str
5
        :type s2: str
6
        :rtype: bool
7
        """
8
        if s1 == s2:
9
            return True
10
        if len(s1) != len(s2):
11
            return False
12

13
        # Check both strings have same count of letters
14
        count1 = collections.defaultdict(int)
15
        count2 = collections.defaultdict(int)
16
        for c1, c2 in zip(s1, s2):
17
            count1[c1] += 1
18
            count2[c2] += 1
19
        if count1 != count2:
20
            return False
21

22
        # Iterate through letters and check if it results in a partition of
23
        # string 1 where the collection of letters are the same
24
        # on the left (non-swapped) or right (swapped) sides of string 2
25
        # Then we recursively check these partitioned strings to see if they are scrambled
26
        lcount1 = collections.defaultdict(int)  # s1 count from left
27
        lcount2 = collections.defaultdict(int)  # s2 count from left
28
        rcount2 = collections.defaultdict(int)  # s2 count from right
29
        for i in xrange(len(s1) - 1):
30
            lcount1[s1[i]] += 1
31
            lcount2[s2[i]] += 1
32
            rcount2[s2[len(s1) - 1 - i]] += 1
33
            if lcount1 == lcount2:  # Left sides of both strings have same letters
34
                if self.isScramble(s1[: i + 1], s2[: i + 1]) and self.isScramble(
35
                    s1[i + 1 :], s2[i + 1 :]
36
                ):
37
                    return True
38
            elif (
39
                lcount1 == rcount2
40
            ):  # Left side of s1 has same letters as right side of s2
41
                if self.isScramble(s1[: i + 1], s2[-(i + 1) :]) and self.isScramble(
42
                    s1[i + 1 :], s2[: -(i + 1)]
43
                ):
44
                    return True
45
        return False