Without ``` if s == s[::-1]: return len(s)```, my following codes got TLE


  • 0
    C
    class Solution(object):
        def longestPalindromeSubseq(self, s):
            """
            :type s: str
            :rtype: int
            """
            if s == s[::-1]:
                return len(s)
    
            N = len(s)
            dp = [[0 for _ in range(N)] for __ in range(N)]
            
            for i in range(N):
                dp[i][i] = 1
                
            for i in range(N-1):
                dp[i][i+1] = 2 if s[i]==s[i+1] else 1
                
                
            for dis in range(2, N):
                for i in range(0, N-dis):
                    j = i+dis
                    if s[i]==s[j]:
                        dp[i][j] = dp[i+1][j-1]+2
                    else:
                        dp[i][j] = max( dp[i+1][j], dp[i][j-1] )
                        
            return dp[0][N-1]
    

    My above codes did from bottom to top. if s == s[::-1]: return len(s) seems only to address the test case with lots of same chars, such as 1000 d's. It is unfair.


Log in to reply
 

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