Python Solution O(n^3) similar to burst balloon with time complexity analysis


  • 0

    In each recursion, you find the last partition that will give you the minimized encoded length just like burst ballon.

    For time complexity, the first step is to count how many subproblems generated by the recursion. The answer is O(n^2) because you just find all different s[start - end] which is O(n^2). For each subproblem, it takes you at most O(n) time to find repeated substring and do string concatenation. Thus, the worst time complexity is O(n^3).

    class Solution(object):
        def encode(self, s, dp = {}):
            """
            :type s: str
            :rtype: str
            """
            if len(s) <= 4:
                return s
            elif s in dp:
                return dp[s]
            dp[s] = s
            idx = (2 * s).find(s, 1)
            if 0 <= idx < len(s):
                dp[s] = str(len(s) / idx) + "[" + self.encode(s[:idx], dp) + "]"
            for i in range(1, len(s)):
                left = self.encode(s[:i], dp)
                right = self.encode(s[i:], dp)
                if len(left) + len(right) < len(dp[s]):
                    dp[s] = left + right
            return dp[s]
    

  • 0
    L

    How did you get O(n^3)? Your for loop recursive function looks worse than n!. Just imagine a large n, you break that up in every partition and then do another recursive call for each part. (1,n-1),(2,n-2)...etc


Log in to reply
 

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