Python solution with detailed explanation


  • 2
    G

    Solution

    Longest Palindromic Subsequence https://leetcode.com/problems/longest-palindromic-subsequence/

    Algorithm

    • LPS(i,j) = LPS(i+1,j-1) + 2 ....................................................s[i] == s[j]
    • LPS(i,j) = max(LPS(i,j-1), LPS(i+1,j)) ....................................s[i] != s[j]
    • LPS(i,j) = 0 .....................................................................................i > j
    • LPS(i,j) = 1 .....................................................................................i = j
    from collections import defaultdict
    class Solution(object):
        def helper(self, i, j, s, cache):
            if i > j:
                return 0
            elif i == j:
                return 1
            elif i in cache and j in cache[i]:
                return cache[i][j]
            elif s[i] == s[j]:
                cache[i][j] = self.helper(i+1, j-1, s, cache) + 2
                return cache[i][j]
            else:
                cache[i][j] = max(self.helper(i, j-1, s, cache), self.helper(i+1, j, s, cache))
                return cache[i][j]
        
        def longestPalindromeSubseq(self, s):
            """
            :type s: str
            :rtype: int
            """
            cache = defaultdict(dict)
            return self.helper(0, len(s)-1, s, cache)
    

  • 0
    N

    The cache = defaultdict(dict) is brilliant.

    I was using (i, j) tuple as the key, as the code shown below, but got Memory Limit Exceeded on the 64 / 83 test case.

    class Solution(object):
        def longestPalindromeSubseq(self, s):
            def helper(i, j):
                if i > j:
                    return 0
                if i == j:
                    return 1
                if (i, j) in cache:
                    return cache[(i, j)]
                    
                if s[i] == s[j]:
                    length = helper(i + 1, j - 1) + 2
                else:
                    length = max(helper(i, j - 1), helper(i + 1, j))
                cache[(i, j)] = length
                return length
            
            cache = {}
            return helper(0, len(s) - 1)
    

  • 0
    C

    @gabbu what is the time complexity?


Log in to reply
 

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