516. Longest Palindromic Subsequence

发表于 | 分类于

每日一题 2019 - 02 - 04

题目：

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

1
"bbbab"

Output:

1
4

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

1
"cbbd"

Output:

1
2

One possible longest palindromic subsequence is “bb”.

解法：

这个题是让我们找出给定字符串中最长的回文数序列的长度，回文序列也即：字符串从前往后遍历与从后往前遍历得到的字符顺序是一样的。

这个题也是一个动态规划的题：

设两个指针i,j,从字符串头开始往后遍历：

  • 如果s[i] == s[j] ,那么bp[i][j] = bp[i+1][j-1]+2，举个例子解释这个递推式子，比如abba这个序列，可以知道最大回文序列长度是4，但是这个4是通过bb找到的，也即找到了bb的前面与后面都是a，进而在bb的基础上加上了2
  • 如果s[i]!=s[j]，那么bp[i][j] = max(bp[i+1][j],bp[i][j-1])，举个例子解释这个递推式子，比如abbc这个序列，可以知道最大回文序列长度是2,这个2是通过bb找到的，但是我们在找c位置时候，发现a、c并不匹配，那么我们就需要把bp[i][j]位置设为前面长度最大的2

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution{
public:
    int longestPalindromeSubseq(string s)
    {
        vector<vector<int>> dp(s.length(),vector<int>(s.length()));
        for(int i=s.length()-1;i>=0;i--)
        {
            dp[i][i]=1;
            for(int j=i+1;j<s.length();j++)
            {
                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][s.length()-1];
    }
};
0%
undefined