给定一个字符串s,找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
输入:
"bbbab"
输出:4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:
"cbbd"
输出:2
一个可能的最长回文子序列为 "bb"。
思路:仍然是动态规划。将字符串横竖列开,变成一个二维数组f,f[ i ][ j ]表示 s
的第 i
个字符到第 j
个字符组成的子串中,最长的回文序列长度是多少。
初始状态:对角线字符都是回文,记为 1。
如果 s 的第 i 个字符和第 j 个字符相同:
f[ i ][ j ] = f[i + 1][j - 1] + 2
如果 s 的第 i 个字符和第 j 个字符不同:
f[ i ][ j ] = max(f[i + 1][ j ], f[ i ][j - 1])
然后注意遍历顺序,i 从最后一个字符开始往前遍历,j 从 i + 1 开始往后遍历,保证每个子问题都已经算好了。
最终返回f[0][n - 1]即可。
class Solution(object):
def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
length = len(s)
f = [[0 for i in range(length)] for j in range(length)]
for i in range(length-1, -1, -1):
f[i][i] = 1
for j in range(i+1, length):
if s[i] == s[j]:
f[i][j] = f[i+1][j-1] + 2
else:
f[i][j] = max(f[i+1][j], f[i][j-1])
return f[0][length-1]
联系客服