Count the number of different palindrome subsequences in the string

author ：Grey

Original address : Count the number of different palindrome subsequences in the string

Problem description

Given a string str, Of course, many subsequences can be generated , Returns how many subsequences are palindromes , Empty sequences are not palindromes , such as ,str = “aba” Palindrome subsequence has

{a}：0 In position a
{a}：2 In position a
{a,a}
{b}
{a,b,a}

So back 5.

Violence solution

Enumerate each subsequence , Then determine whether the subsequence is a palindrome , The code is as follows

    public static int ways1(String str) {
    
        if (str == null || str.length() == 0) {
    
            return 0;
        }
        char[] s = str.toCharArray();
        char[] path = new char[s.length];
        return process(str.toCharArray(), 0, path, 0);
    }
    //  Enumerate each location to or from , Get the number of palindrome subsequences 
    public static int process(char[] s, int si, char[] path, int pi) {
    
        if (si == s.length) {
    
            return isP(path, pi) ? 1 : 0;
        }
        int ans = process(s, si + 1, path, pi);
        path[pi] = s[si];
        ans += process(s, si + 1, path, pi + 1);
        return ans;
    }
    //  Judge path In a string 0...pi-1 Is it a palindrome 
    public static boolean isP(char[] path, int pi) {
    
        if (pi == 0) {
    
            return false;
        }
        int L = 0;
        int R = pi - 1;
        while (L < R) {
    
            if (path[L++] != path[R--]) {
    
                return false;
            }
        }
        return true;
    }

Dynamic programming solution

Define a two-dimensional array dp, The array length is assumed to be n

int[][] dp = new int[n][n]

dp[i][j] The meaning is ： character string [i...j] The maximum number of palindrome subsequences that can be obtained in the interval , therefore ,dp[0][n-1] The value of is the final answer we need to find .

according to dp The meaning of array , We can get , Two dimensional matrix dp The values on the diagonals in are all 1, The position above the diagonal can also be easily obtained , See note below

//  The values on the diagonal are all 1
for (int i = 0; i < n; i++) {
    
    dp[i][i] = 1;
}
//  The position above the diagonal , namely dp[i][i+1] Value on 
//  If str[i] == str[i+1], such as ：aa, There are three palindrome subsequences , Namely {a},{a},{aa}
//  If str[i] != str[i+1], such as ：ab, There are two palindrome subsequences , Namely  {a},{b}
for (int i = 0; i < n - 1; i++) {
    
    dp[i][i+1] = str[i] == str[i+1] ? 3 : 2;
}

Next, consider the general location dp[i][j], There can be several situations as follows ：

Situation 1 ,i The character of position is discarded , that dp[i][j] = dp[i+1][j];

Situation two ,j The character of position is discarded , that dp[i][j] = dp[i][j-1];

Based on case one and case two ,

dp[i][j] = dp[i+1][j] + dp[i][j-1]

This is the time , In fact, it is a heavy part , The heavy part is dp[i+1][j-1], therefore

dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

If str[i] == str[j], Then there is case three , Case III medium ,str[i] and str[j] But keep it all , And interval [i+1...j-1] Form palindrome string ,str[i] It can also be used alone with str[j] Form a palindrome string . therefore , Situation three

// dp[i][j] In two parts 
//  among :
//  The first part ：dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]  Express i Location and j When the position is abandoned , The number of answers obtained 
//  The second part ：dp[i + 1][j - 1] + 1  In case 3 , Use at the same time str[i] and str[j] The number of answers from the position 
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] +  dp[i + 1][j - 1]  + 1

Dynamic programming solution of the complete code

    public static int ways2(String s) {
    
        if (s == null || s.length() == 0) {
    
            return 0;
        }
        char[] str = s.toCharArray();
        int n = str.length;
        int[][] dp = new int[n][n];
        //  The diagonals are 1
        for (int i = 0; i < n; i++) {
    
            dp[i][i] = 1;
        }
        for (int i = 0; i < n - 1; i++) {
    
            dp[i][i + 1] = str[i] == str[i + 1] ? 3 : 2;
        }
        for (int i = n - 3; i >= 0; i--) {
    
            for (int j = i + 2; j < n; j++) {
    
                //  subtract dp[i+1][j-1] It's because it's repeated 
                dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                if (str[i] == str[j]) {
    
                    // dp[i][j] In two parts 
                    //  among :
                    //  The first part ：dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]  Express i Location and j When the position is abandoned , The number of answers obtained 
                    //  The second part ：dp[i + 1][j - 1] + 1  In case 3 , Use at the same time str[i] and str[j] The number of answers from the position 
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] +  dp[i + 1][j - 1]  + 1;
                }
            }
        }
        return dp[0][n - 1];
    }

Similar problems

LeetCode 730. Statistics of different palindrome subsequences

more

Algorithm and data structure notes