题目描述

给定一个字符串s，找到其中最长的回文子序列

示例 1: 输入:

"bbbab"

输出:

4

一个可能的最长回文子序列为 “bbbb”。

# -*- coding: utf-8 -*-
# @Time         : 2019-10-11 11:58
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : longestPalindromicSubsequence.py
# @Blog         : https://sysujayce.github.io/
# @Github       : https://github.com/SysuJayce


class Solution:
    """
    dp[i][j]表示s[i: j + 1]的最长回文子序列长度

    若s[i] == s[j]，则dp[i][j] = dp[i + 1][j - 1] + 2 【即将头尾去掉】
    若s[i] != s[j]，则dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 【即分别去头和去尾，求最大】

    dp[i][i] = 1，因为s[i: i + 1]总是一个回文字符串，长度为1
    """
    def longestPalindromeSubseq(self, s: str) :
        if len(s) < 2 or s == s[:: -1]:
            return len(s)

        dp = [[0] * len(s) for _ in range(len(s))]
        for j in range(len(s)):  # col
            # 逐列填充矩阵
            dp[j][j] = 1
            for i in reversed(range(j)):  # row
                # 从对角线开始往上填充
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        # 最后矩阵的右上角就是所求的长度
        return dp[0][-1], self.findPalindrome(dp, s)

    def findPalindrome(self, dp, s):
        """
        要从已经计算好的状态矩阵中找出所有的最长公共子序列，我们需要关注的是当出现向上和向左都可以
        的时候，需要保持方向的一致，向上就一直向上，向左就一直向左，否则会出现问题。
        """
        rows, cols = len(dp), len(dp[0])
        i, j = 0, cols - 1
        ans = ''
        while i < rows and j >= 0:
            # 因为我们是反向查找的，所以加到前面去
            if dp[i][j] == 0 or dp[i][j] > dp[i + 1][j]:
                ans = s[i] + ans
                i += 1
                j -= 1
            else:
                i += 1
        return ans


def main():
    solution = Solution()
    s = 'axbdba'
    length, palindrome = solution.longestPalindromeSubseq(s)
    print(length)
    print(palindrome)


if __name__ == '__main__':
    main()