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

• 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]
``````

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

• 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];
``````

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

• why "bbabb" is not a palindromic ?

• now the solution is TLE, don't know why

• @jsqihui300k yeah, me too

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

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

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

• @jedihy thanks, I know my mistake

• using '%2' rocks!

• This post is deleted!

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