Fast and concise Python solution that actually gets AC


  • 10
    O

    I noticed that some of the most voted python solutions here got TLE, so here is an optimized solution.

    class Solution(object):
        def longestPalindromeSubseq(self, s):
            d = {}
            def f(s):
                if s not in d:
                    maxL = 0    
                    for c in set(s):
                        i, j = s.find(c), s.rfind(c)
                        maxL = max(maxL, 1 if i==j else 2+f(s[i+1:j]))
                    d[s] = maxL
                return d[s]
            return f(s)
    

  • 0
    W

    @o_sharp

    Not DP but a awesome solution!

    Your memoization is good. And finding the left, right indices of a same character actually handled the infamous test case like"ffffff...fff" perfectly.


Log in to reply
 

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