Python DP O(n) space O(n^2) time


  • 12

    Idea:
    dp[i][j] = longest palindrome subsequence of s[i to j].
    If s[i] == s[j], dp[i][j] = 2 + dp[i+1][j - 1]
    Else, dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    Rolling array O(2n) space

    class Solution(object):
        def longestPalindromeSubseq(self, s):
            """
            :type s: str
            :rtype: int
            """
            n = len(s)
            dp = [[1] * 2 for _ in range(n)]
            for j in xrange(1, len(s)):
                for i in reversed(xrange(0, j)):
                    if s[i] == s[j]:
                        dp[i][j%2] = 2 + dp[i + 1][(j - 1)%2] if i + 1 <= j - 1 else 2
                    else:
                        dp[i][j%2] = max(dp[i + 1][j%2], dp[i][(j - 1)%2])
            return dp[0][(n-1)%2]
    

    Further improve space to O(n)

    class Solution(object):
        def longestPalindromeSubseq(self, s):
            """
            :type s: str
            :rtype: int
            """
            n = len(s)
            dp = [1] * n
            for j in xrange(1, len(s)):
                pre = dp[j]
                for i in reversed(xrange(0, j)):
                    tmp = dp[i]
                    if s[i] == s[j]:
                        dp[i] = 2 + pre if i + 1 <= j - 1 else 2
                    else:
                        dp[i] = max(dp[i + 1], dp[i])
                    pre = tmp
            return dp[0]
    

  • 0

    @jedihy the O(n) space, just incredible!


  • 0
    I

    JAVA version, 37ms, beats 99.5%.

            int n = s.length();
            int[] dp = new int[n];
            for (int j = 0; j < n; ++j) {
                dp[j] = 1;
                int prev = 0;
                for (int i = j - 1; i >= 0; --i) {
                    int tmp = dp[i];
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i] = 2 + prev;
                    } else {
                        dp[i] = Math.max(dp[i + 1], dp[i]);
                    }
                    prev = tmp;
                }
            }
            return dp[0];
    

  • 1
    C

    could you explain the O(n) and O(2n) solution? I didn't understand them.


  • 0

    why "bbabb" is not a palindromic ?


  • 0
    J

    now the solution is TLE, don't know why


  • 0
    C

    @jsqihui300k yeah, me too


  • 0

    @codies Are you implying that there is a better solution?


  • 0
    C

    @jedihy nope, just because the spatial locality in python arrays must be taken care of


  • 0

    @codies My O(n) still can get accepted. I tried several mins ago.


  • 0
    C

    @jedihy thanks, I know my mistake


  • 0
    W

    using '%2' rocks!


Log in to reply
 

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