首页 > 代码库 > 516. Longest Palindromic Subsequence

516. Longest Palindromic Subsequence

本周课堂上学习的是动态规划,因此在LeetCode上找到相应的题进行练习。

 

题目:

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

(给定一个字符串S,找到它的最长回文子序列长度)

 

示例:

Example 1:
Input  :"bbbab"

Output:4

(One possible longest palindromic subsequence is "bbbb".)

Example 2:
Input:"cbbd"

Output:2

(One possible longest palindromic subsequence is "bb".)

 

代码:

class Solution {
public:
    int longestPalindromeSubseq(string s) 
    {
        int n = s.length();
        vector<vector<int> > vec(n,vector<int>(n,0));
        
        for(int i =0 ;i < n;i++)
            vec[i][i] = 1;

        for(int j = 1; j < n; j++){   //j从1开始
            for(int i = j - 1; i >= 0; i--){
                if(s[i] == s[j]){
                    //只要s[i] = s[j] 就说明s[i:j]是一个回文序列
                    //判断i与j之间还有没有别的子串
                    vec[i][j] = i + 1 <= j - 1 ? 2 + vec[i + 1][j - 1] : 2;
                }
                else{
                    //s[i+1:j] s[i:j+1]之间的最长子串
                    vec[i][j] = max(vec[i + 1][j], vec[i][j - 1]);
                }
            }
        }
        return vec[0][n - 1];
    }
};

 

题解:

  “寻找关于xxx的最大的子串/序列”是经典的动态规划问题。在这道题中,s[i]到s[j]之间(以下简称s[i:j])的最长回文子串就是一个状态,最终要求的状态是s[0:n-1]。状态可以通过一个二维vector(vec)来表示,状态之间的转换思路是:判断s[i:j]的第一个与最后一个元素(实际就是s[i]与s[j])是否相等,如果是,说明s[i:j]相比于上一个状态,可以更新,然后就判断i与j之间还有没有别的元素,如果没有的话,vec[i][j]就是2,否则,就是vec[i+1][j-1]+2(实际上就是s[i+1:j-1]的最长回文子串)。

  而如果s[i:j]的第一个与最后一个元素不相等,说明状态不用更新,vec[i][j]等于vec[i][j-1]与vec[i+1][j]之间的较大值,因为实际上s[i+1:j]与s[i:j-1]都有可能是在当前状态下的最长子串,举个例子,比如当要计算aaaab中s[0:4]最长回文子串,此时答案是s[0:3]但如果是baaaa,就应该是s[1:4]。

  这种解法的时间复杂度与空间复杂度都很明显为O(n^2),不再赘述。

516. Longest Palindromic Subsequence