Simple to understand Python recursive solution


  • 4
    A
    from collections import Counter
    class Solution(object):
        def isScramble(self, s1, s2):
            if s1 == s2: return True
            if Counter(s1) != Counter(s2): return False # early backtracking
            for i in xrange(1,len(s1)):
                if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])): return True
                if (self.isScramble(s1[:i], s2[-(i):]) and self.isScramble(s1[i:], s2[:-(i)])): return True
            return False

  • 0
    B

    Why Counter is faster than len?If I replace Counter with len , then I get time limtit exceed.


  • 0
    B

    May I ask how to analyze the time complexity of this?


  • 0

    @alexj why do you use parens in the indices when slicing?


  • 0

    @BookChan Because it allows to eliminate more non-scrambled strings earlier on, you terminate earlier on that branch of recursion and so runtime is much better.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.