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


  • 0
    M

    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
                while(i+ss<strlen):
                    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.