Avoid TLE. Naive python code beats 98.25%

  • 0

    I got TLE with standard dp. The work around is to check the whether the given string itself is a palindrome and use O(N) space.

    class Solution(object):
        def longestPalindromeSubseq(self, s):
            :type s: str
            :rtype: int
            if s == s[::-1]:
                return len(s)
            s_len = len(s)
            dp = [0 for _ in xrange(s_len)]
            dp[-1] = 1
            for i in xrange(s_len-1,-1,-1):
                newdp = dp[:]
                newdp[i] = 1
                for j in xrange(i+1,s_len):
                    if s[i] == s[j]:
                        newdp[j] = dp[j-1]+2
                        newdp[j] = max(dp[j],newdp[j-1])
                dp = newdp
            return dp[s_len-1]

Log in to reply

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