O(n^2) solution. Got "time limit exceeded"

  • 0

    The topological order of subproblems is based on the length of the substring.

    class Solution(object):
        def longestPalindromeSubseq(self, s):
            :type s: str
            :rtype: int
            strlen = len(s)
            LPS = [[1]*strlen for _ in range(strlen)]    
            for i in xrange(strlen-1):
                LPS[i][i+1] = 2 if s[i] == s[i+1] else 1
            for ss in xrange(2, strlen):
                i = 0
                    if s[i] == s[i+ss]: LPS[i][i+ss] = LPS[i+1][i+ss-1] + 2
                    else: LPS[i][i+ss] = max( LPS[i+1][i+ss], LPS[i][i+ss-1])
                    i += 1
            return LPS[0][strlen-1]

Log in to reply

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