Calculate the number of palindrome sub-sequence for a given string.


  • 0
    W

    Given a string s, calculate the number of palindrome sub-sequence. For example, s = "aba", there are 5 palindrome sub-sequence: "a", "a", "aa", "b", "aba". Note that two identical sub-sequences are counted separately if at least one element has different positions in s.

    More example:
    ccc, then the answer is 7.

    class Solution{
    public:
        int getNumberOfPalindromeSubsequence(string str){
            auto len = str.size();
            vector<vector<int> > dp(len, vector<int>(len, 0));
            for(int i = 0; i < len; i++)    dp[i][i] = 1;
            for(int j = 1; j < len; j++){
                for(int i =0; i + j < len; i++){
                    dp[i][i + j] = dp[i][i + j - 1] + dp[i + 1][i + j] - dp[i + 1][i + j - 1];
                    if(str[i] == str[i + j]){
                        dp[i][i + j] += 1 + dp[i + 1][i + j - 1];
                    }
                }
            }
    
            return dp[0][len - 1];
        }
    };
    

    My tests:

    Solution s;
    assert(s.getNumberOfPalindromeSubsequence("aba") == 5);
    assert(s.getNumberOfPalindromeSubsequence("abcbaddabcba") == 277);
    assert(s.getNumberOfPalindromeSubsequence("12111112351121") == 1333);
    assert(s.getNumberOfPalindromeSubsequence("ccccccc") == 127);
    assert(s.getNumberOfPalindromeSubsequence("fdadfa") == 17);
    return 0;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.