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:longest + 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?