Scramble String

Problem: Scramble String

A is a scramble string of B when their substrings are scramble strings of each other, and the corresponding relationship can be swapped.

Another faster solution checks characters of strings first.

Code in Python:

class Solution(object):

    def __init__(self):
        self.cache = {}

    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        key = s1 + "," + s2
        if key in self.cache: return self.cache[key]

        if s1 == s2:
            self.cache[key] = True
            return True
        n = len(s1)
        if n == 1:
            self.cache[key] = False
            return False

        for i in xrange(1, n):
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
                self.cache[key] = True
                return True
            if self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):
                self.cache[key] = True
                return True

        self.cache[key] = False
        return False