Leetcode 87. Scramble String

https://leetcode.com/problems/scramble-string/

DFS is the right tool for this problem.

Solution:

# T:O(n^4) S:O(n^3)
class Solution:
    # @return a boolean
    def isScramble(self, s1, s2):
        if len(s1)!=len(s2): return False
        if s1==s2: return True
        l1, l2=list(s1), list(s2)
        l1.sort()
        l2.sort()
        if l1!=l2: return False
        length=len(s1)
        for i in range(1,length):
            if self.isScramble(s1[:i],s2[:i]) and\
            self.isScramble(s1[i:],s2[i:]): return True
            if self.isScramble(s1[:i],s2[length-i:]) and\
       self.isScramble(s1[i:],s2[:length-i]): return True
        return False

Run Time: 84 ms