即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

leetcode516. Longest Palindromic Subsequence

编程语言 dike1993 35℃ 0评论
本文目录
[隐藏]

1.题目

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:

“bbbab”

Output:

4

One possible longest palindromic subsequence is “bbbb”.

Example 2:


Input:

“cbbd”

Output:

2

One possible longest palindromic subsequence is “bb”.

2.思路

这个题目跟Longest Palindromic Substring,有些类似,主要区别就是,子串必须是连续的,而子序列可以不连续。很明显依然用dp来做,只是转换方程有些差异,初始化的两个方程是类似的P(i,i)= 1,P(i,i+1)=2 (S[i]= S[i+1])else P(i,i+1)=1 ,状态转移方程为P(i,j)=max(P(i,j-1),P(i+1,j),P(i+1,j-1)+2) (S[i]= S[j]),P(i,j)=max(P(i,j-1),P(i+1,j),P(i+1,j-1)) (S[i]!= S[j]),每个新的状态都可以由三个旧状态转换而来。

3.代码


class Solution {
public:
    int longestPalindromeSubseq(string s) {
        //空串
        if (s.empty()) 
        return 0;

        int n=s.length();
        //table[i][j]表示s中i-j的回文子序列的最大长度。
        int table[1000][1000]={0};

        for (int len=1; len<=n; len++) {
            for (int lhs=0; lhs+len<=s.size(); lhs++) {
                int rhs = lhs+len-1;
                if (lhs == rhs) {
                    table[lhs][rhs] = 1;
                } else if (lhs+1 == rhs) {       //以上两种情况是初始化状态
                    table[lhs][rhs] = (s[lhs] == s[rhs]) ? 2 : 1;  
                } else {
                    int add = s[lhs] == s[rhs] ? 2 : 0;
                    table[lhs][rhs] = max(max(table[lhs][rhs-1], table[lhs+1][rhs]), table[lhs+1][rhs-1] + add);
                }
            }
        }

        return table[0][n-1];
    }
};

转载请注明:CodingBlog » leetcode516. Longest Palindromic Subsequence

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情