DP Python (explained in detail) TLE on test case "ddd..."


  • 0
    S

    Hello! I saw many posts about Time Limit Exceeded with a Dynamic Programming solution, so I was wondering if I could get some help with mine. High level overview (rough) of my solution is:

    for substring lengths 1 to n (where n is the length of the given string),
    -- for all substrings of this length
    ---- check if the substring is a palindrome (using string indices, otherwise slicing the string will make the check linear time). If it is, store the indices in a set ("memoize") so that when we're checking bigger substrings on next iterations, we can check if the smaller ones are in the set in constant time.
    return the longest substring

    And here it is in code:

    class Solution(object):
        def longestPalindrome(self, s):
            longest = (0, 0)
            memo = set()
            for substring_length in xrange(1, len(s) + 1): # start with smaller substrings and memoize
                for i in xrange(0, len(s) - substring_length + 1): # e.g. for s = 'abcde' and substring_length = 2, i goes from
                    sub_indices = (i, i + substring_length - 1) #  0 to 3 and sub_indices will be (0, 1), (1, 2) ...
                    if self.is_palindrome(sub_indices, memo, s):
                        longest = sub_indices
            return s[longest[0]:longest[1] + 1]
        
        def is_palindrome(self, indices, memo_set, s):
            i, j = indices
            if j - i <= 1: # 2 or less characters
                if s[i] == s[j]:
                    memo_set.add(indices)
                    return True
                return False
            if s[i] == s[j] and (i + 1, j - 1) in memo_set:
                memo_set.add((i, j))
                return True
            return False        
    

    I have 2 for loops and my is_palindrome method clearly takes constant time, so this solution seems to be O(N^2). Am I missing something? If not, why does this fail on the 'ddd...' test case?


Log in to reply
 

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