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

[DP]516. Longest Palindromic Subsequence

编程语言 Rewind_L 38℃ 0评论

题目:

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

题目分析:

1、根据题目很容易看出题目要求求出一个字符串的最长回文子序列。

2、这里最重要的一点是:求解回文子序列的过程中,如果采用两头向中间的方法,倘若两头相同,则可以直接将两头取出当作回文子序列的一部分(例如“abbaba”可以直接取出两头的‘a’,再计算“bbab”)而不用担心这样的操作会遗漏某些更优解(但不排除有别的最优解)。

3、有了2中的理论基础,利用一个函数f,参数包括字符串s以及用来指明当前要计算的字串左右下标L和R。结束条件为L == R或L + 1 == R。若没有满足结束条件,则比较字符串两头的元素s[L] == s[R]是否成立。若成立则取出再计算除去两头的字串;若不成立则分别取出左右元素计算取出后字串的结果大小,取大者作为返回值。

代码1:

int f(string &s, int locL, int locR){ //假设f(s,loc,len)表示字符串s以下标locL开始locR结尾区间最长的子序列长度。
    if(locL == locR)
        return 1;
    else if(locL > locR)
        return 0;
    else{
        if(s[locL] == s[locR])
            return 2 + f(s, locL + 1, locR - 1);
        else
            return max(f(s, locL + 1, locR), f(s, locL, locR - 1));
    }
     
}

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        return f(s, 0, s.size() - 1);
    }
};

4、代码1经测试算法无误。但是提交后出现超时的情况,说明算法仍然存在缺陷。仔细检查后发现:在函数f的最后一个讨论情况中,比较L+1和R-1的情况中分别可能出现L+2,L+1/R-1和L+1/R-1,R-2的子情况,如果发生就意味着L+1/R-1这种情况被计算了两次,可能会浪费大量的空间和时间,所以要避免这种重复计算的发生。

5、针对上面发现的问题,考虑每个区间段的答案采用一个二维数组保存下来。二维数字初始化为0,表示未被计算【只要经过计算则不可能为0,最少为1】,如果在计算L+1或者R-1的时候遇到对应数组元素的值不为0时,则不需要再次计算,直接取出该值。这样就避免了重复计算的情况。

6、具体的二维数组采用vector> m的形式来实现而不是int m[][],因为函数并不支持引入未指明界限的二元数组。

代码2:

void f(string &s, int L, int R, vector> &m){
    if(L == R)
        m[L][R] = 1;
    else if(L + 1 == R)
        m[L][R] = (s[L] == s[R]? 2 : 1);
    else if(s[L] == s[R]){
        f(s, L + 1, R - 1, m);
        m[L][R] = 2 + m[L + 1][R - 1];
    }
    else{
        if(m[L + 1][R] == 0)
            f(s, L + 1, R, m);
        if(m[L][R - 1] == 0)
            f(s, L, R - 1, m);
        m[L][R] = max(m[L + 1][R], m[L][R - 1]);
    }

}

class Solution {
public:
    int longestPalindromeSubseq(string s){
        vector> m;
        for(int i = 0; i < s.size(); i++){
            vector temp;
            for(int j = 0; j < s.size(); j++)
                temp.push_back(0);
            m.push_back(temp);
        }
        f(s, 0, s.size() - 1, m);
        return m[0][s.size() - 1];
    }
};


转载请注明:CodingBlog » [DP]516. Longest Palindromic Subsequence

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

*

表情