描述

给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。
注：回文序列是指这个序列无论从左读还是从右读都是一样的。
本题中子序列指字符串任意位置删除k（len(s)>=k>=0)个字符后留下的子串。

数据范围：字符串长度满足NC154 最长回文子序列 - 图4，
进阶：空间复杂度NC154 最长回文子序列 - 图5，时间复杂度NC154 最长回文子序列 - 图6。

示例1

输入："abccsb"
输出：4
说明：最长回文子串是"bccb"

示例2

输入："abcdewa"
输出：3
说明：最长回文子串是"aba"或"aca"或"ada"或"aea"或"awa"

解决思路：转化为求字符串和其逆序的最长公共子序列的长度

设字符串s的逆字符串为sn，定义二维数组dp，dp[i][j]表示子串s[0:i]和子串sn[0:j]的最长公共子序列的长度。

  • 如果s[i]=sn[j]，dp[i][j]=dp[i-1][j-1]+1；
  • 否则，dp[i][j]=max(dp[i-1][j], dp[i][j-1])。

    复杂度分析：时间复杂度NC154 最长回文子序列 - 图7，空间复杂度NC154 最长回文子序列 - 图8。

    实现代码

    1. class Solution {
    2. public:
    3.   /**
    4.    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    5.    *
    6.    * 
    7.    * @param s string 一个字符串由小写字母构成，长度小于5000
    8.    * @return int
    9.    */
    10.   int longestPalindromeSubSeq(string s) {
    11.       // 转化为求s和s逆序的最长公共子序列
    12.       int n = s.length();
    13.       vector<vector<int> > dp(n+1, vector<int>(n+1, 0));
    14.       for(int i=1; i<=n; i++){
    15.           for(int j=1; j<=n; j++){
    16.               if(s[i-1] == s[n-j]){
    17.                   dp[i][j] = dp[i-1][j-1] + 1;
    18.               }
    19.               else{
    20.                   dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    21.               }
    22.           }
    23.       }
    24.       return dp[n][n];
    25.   }
    26. };

    运行效率