leetcode-go/leetcode/hard/730-slow.cc

#include <cstring>
#include <iostream>
#include <string>

using std::string;
using std::cout; using std::endl;


// for 'a' ~ 'd'
static const int X_MAX = 'd' - 'a';
static const int N_MAX = 1000;
static int dp[3][N_MAX][N_MAX][X_MAX + 1];

class Solution {
private:
    static const int MOD = 1000000007;

public:
    int countPalindromicSubsequences(string S) {
        int n = S.size(), ans = 0, memset_size = sizeof(dp[0]);
        memset(dp, 0, sizeof(dp));
        for (int len = 1; len <= n; len++) {
            for (int sep = len - 1; sep < n; sep ++) {
                for (int i = 0; i + sep < n; i++) {
                    int j = i + sep;
                    int a = S[i] - 'a', b = S[j] - 'a';
                    for (int x = 0; x <= X_MAX; x++)
                        if (x != a && x != b && 1 < sep)
                            dp[0][i][j][x] = dp[0][i + 1][j - 1][x];
                    if (a == b) {
                        if (len <= 2)
                            dp[0][i][j][a] = 1;
                        else
                            for (int x = 0; x <= X_MAX; x++)
                                dp[0][i][j][a] = (dp[0][i][j][a] + dp[2][i + 1][j - 1][x]) % MOD;
                    } else if (0 < sep) {
                        dp[0][i][j][a] = dp[0][i][j - 1][a];
                        dp[0][i][j][b] = dp[0][i + 1][j][b];
                    }
                }
            }
            for (int x = 0; x <= X_MAX; x++)
                ans = (ans + dp[0][0][n - 1][x]) % MOD;
            // Use scrolling array to save memory
            memcpy(dp[2], dp[1], memset_size);
            memcpy(dp[1], dp[0], memset_size);
            memset(dp[0], 0, memset_size);
        }
        return ans;
    }
};


// Input: 
// S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
// Output: 104860361

// bccb
// len 0:
// len 1: b c
// len 2: bb cc
// len 3: bcb
// len 4: bccb

// dp[1][0][0]['b'] = 1, dp[1][1][1]['c'] = 1, dp[1][2][2]['c'] = 1, dp[1][3][3]['b'] = 1

// dp[len][i][j][x] means different palindroms count which start / end with 'x' between s[i] and s[j], length is len
// loop len, sep, i
// j = i + sep
// for x != s[i] and x != s[j]:
//                   dp[len][i][j][x] = dp[len][i + 1][j - 1][x]
// s[i] == s[j] == a:
//                   dp[len][i][j][a] = sum(dp[len - 2][i + 1][j - 1][every x])
// s[i] == a, s[j] == b, a != b:
//                   dp[len][i][j][a] = dp[len][i][j - 1][a],
//                   dp[len][i][j][b] = dp[len][i + 1][j][b]


int main() {
    Solution* sol = new Solution;
    string input;

    input = "addd";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 4 << endl;

    input = "bccb";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 6 << endl;

    input = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 104860361 << endl;

    input = "baaddaaabaddccbbbdcbcccbdbdabdabdbadabddbbcbbcabbccdaccdbcbbcdcdbaadbcadacabcaaaadbcaddbbacddcdabaadcacacdcabaadacadcccdcbbcdabdcdacaacdcdbdacbdbcdcbaddaccabaaaabcadacdaddbcccbcdbadbdddaaabbdbdbcbcdab";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 431300010 << endl;

    input = "bdccbdbdcaacaadbdacaadabbdaababacbdbadaccccbbbccbdbddcacdbbcdaaababddadbbcabaddbbaabcdacdcddcbacdcadddbaadcbbccdcbdcaaabcbddacaccadacdcadacadccabdbadcdabaaccbcabbacdcbbbabddbcccbcbcddacaccabbabccdbbabacadbbdbcccbddaaadcdaddcccddaacbddabddabadbcbaadcaddbdccabaddcccdccbacaccccbcdccacbabddcbcbbbdbbddaabbcaddbddddaacbbccbcdbadacccbadbccdddadcbacbbdcabcbdbbaabcdcbdacabacdccdaabcbbddbdddcacdbdccbbabbaccdcbabcdacdabdddaddacdbddabcbbbdcccacbdadddbbdbcabccadbcbadddcbcddaababcabbbcbbabadaddabcbdacaadcababcbacadcdabcdbddadaadddddbaaacddaacadcdbaaacbacaabdabccbacabbabddacddcdacdcddbacbddbdcadcddabdadcdbcbbcadbcdabbbbdcdadadbbcadbcbbcccccabdaabcdacbdbcadabcdbaaaaacdaaabcdcaabddcacdcacabbaadbdbcbaaabadbdadadaccddacababbdcbaaaccaabbdaddadcabaabbdaadadcabcabbdbbdccbabbbabbcbcbdcacccbdbabdbaadccdaddaddaadadccabdcbbbccacbbaaabccaccdcabbbddbdbbacdaabbdcdacbdddbacbadccabbbdbbbdbdbcadcacddddcdbdcabccdccabaadbcbacaaababdddcbcdaaabaaabddbcabcbbcdddccdcbccbbccadccaaccccbdadcaacdcbcabacacadaabacddaadcccbcabdad";
    cout << "actual: " << sol->countPalindromicSubsequences(input) << ", expected: " << 739921586 << endl;

    return 0;
}