Accepted Python DP solution. What's the time complexity of this solution?

  • 1

    class Solution:
    # @return a boolean
    def init(self):
    self.cache = {}

    def isScramble(self, s1, s2):
        if (s1, s2) in self.cache:
            return self.cache[(s1, s2)]
        if len(s1) == 1:
            self.cache[(s1,s2)] = (s1 == s2)
            return self.cache[(s1,s2)]
        length = len(s2)
        for i in range(1, length): #split point 1~len(s2)-1
            if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])) \
                or (self.isScramble(s1[length-i:], s2[:i]) and self.isScramble(s1[:length-i], s2[i:])):
                self.cache[(s1,s2)] = True
                return True
        self.cache[(s1,s2)] = False
        return False

    I used Memoization DP. But I don't know if this solution is good enough. I think the time complexity is exponential as O(4^(length of string)), is it?
    Any way to improve this solution?

Log in to reply

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