LWC 59:730. Count Different Palindromic Subsequences

LWC 59:730. Count Different Palindromic Subsequences

传送门:730. Count Different Palindromic Subsequences

Problem:

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7. A subsequence of a string S is obtained by deleting 0 or more characters from S. A sequence is palindromic if it is equal to the sequence reversed. Two sequences A_1, A_2, … and B_1, B_2, … are different if there is some i for which A_i != B_i.

Example 1:

Input: S = ‘bccb’ Output: 6 Explanation: The 6 different non-empty palindromic subsequences are ‘b’, ‘c’, ‘bb’, ‘cc’, ‘bcb’, ‘bccb’. Note that ‘bcb’ is counted only once, even though it occurs twice.

Example 2:

Input: S = ‘abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba’ Output: 104860361 Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.

Note:

The length of S will be in the range [1, 1000].

Each character S[i] will be in the set {‘a’, ‘b’, ‘c’, ‘d’}.

思路: 难点在于如何划分子问题,才能保证更新dp时没有重复,其中需要解决重复元素子串的表达。为了保证每个子问题的回文在原问题中没有出现过,定义如下规则:子问题求出的回文串必须套上一层外壳,即子问题中的回文串集合Set = {s | s 为回文}, 有新的回文 s’ = “a” + s + “a” or “b” + s + “b”,….

定义函数如下f(i, j) 表示当前对应S[i,…j]的不重复回文串个数,于是有:

初始化: ans = 0
1. 子问题的回文串批层外衣,有 ans += f(i + 1, j - 1) , 其中S[i] == S[j]
2. 考虑"a_..._a", "_..._"表示子问题的回文串,抽出a'= a...a,其中"..."表示x个a,那么有新的回文串aa...a 和 aa...aa,有ans += 2

代码如下:

    public int countPalindromicSubsequences(String S) {
        int n = S.length();
        int[][] next = new int[4][1010];
        int[][] prev = new int[4][1010];

        char[] cs = S.toCharArray();

        for (int i = 0; i < 4; ++i) Arrays.fill(next[i], n);
        for (int i = n - 1; i >= 0; --i) {
            int c = cs[i] - 'a';
            for (int j = 0; j < 4; ++j) next[j][i] = i + 1 == n ? n : next[j][i + 1];
            next[c][i] = i;
        }

        for (int i = 0; i < 4; ++i) Arrays.fill(prev[i], -1);
        for (int i = 0; i < n; ++i) {
            int c = cs[i] - 'a';
            for (int j = 0; j < 4; ++j) prev[j][i] = i - 1 == -1 ? -1 : prev[j][i - 1];
            prev[c][i] = i;
        }
        dp = new int[1010][1010];
        return f(cs, next, prev, 0, n - 1);
    }

    int mod = 1000000000 + 7;
    int[][] dp;

    int f(char[] cs, int[][] next, int[][] prev, int s, int e) {
        if (s > e) return 0;
        if (dp[s][e] > 0) return dp[s][e];
        long ans = 0;
        for (int i = 0; i < 4; ++i) {
            int ns = next[i][s];
            int ne = prev[i][e];
            if (ns > ne) continue;
            if (ns != ne) ans += 1;
            ans ++;
            ans += f(cs, next, prev, ns + 1, ne - 1);
        }
        dp[s][e] = (int)(ans % mod);
        return dp[s][e];
    }    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习入门

LWC 63:748. Shortest Completing Word

LWC 63:748. Shortest Completing Word 传送门:748. Shortest Completing Word Problem: ...

1889
来自专栏ml

cf(#div1 B. Dreamoon and Sets)(数论)

B. Dreamoon and Sets time limit per test 1 second memory limit per test 256 ...

2947
来自专栏小樱的经验随笔

POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

3437
来自专栏机器学习入门

LWC 55:712. Minimum ASCII Delete Sum for Two Strings

LWC 55:712. Minimum ASCII Delete Sum for Two Strings 传送门:712. Minimum ASCII Dele...

2147
来自专栏HansBug's Lab

1297: [SCOI2009]迷路

1297: [SCOI2009]迷路 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 652  Solved:...

2605
来自专栏算法修养

CodeForces 17E Palisection(回文树)

E. Palisection time limit per test 2 seconds memory limit per test 128 meg...

3204
来自专栏数据结构与算法

图论算法模板整理及思路 不断更新 绝对精品

DFS 1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 using nam...

3646
来自专栏算法修养

HDU 1403 Eight&POJ 1077(康拖,A* ,BFS,双广)

Eight Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Ja...

2787
来自专栏ml

hdu----(1849)Rabbit and Grass(简单的尼姆博弈)

Rabbit and Grass Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/3...

3367
来自专栏小樱的经验随笔

ZOJ 1403&&HDU 1015 Safecracker【暴力】

Safecracker ---- Time Limit: 2 Seconds      Memory Limit: 65536 KB ---- === Op t...

3106

扫码关注云+社区