# LWC 59：730. Count Different Palindromic Subsequences

## LWC 59：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:

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’}.

```初始化： 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];
}    ```

98 篇文章33 人订阅

0 条评论

## 相关文章

7127

1304

### 提高 golang 的反射性能

golang 的反射很慢。这个和它的 api 设计有关。在 java 里面，我们一般使用反射都是这样来弄的。 ---- Field field = clazz....

4065

1031

### Code forces 719A Vitya in the Countryside

A. Vitya in the Countryside time limit per test:1 second memory limit per test:2...

3336

### HDU----（3294）Girls' research（manacher）

Girls' research Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3...

2675

### （三）dict哈希结构3

/* This function performs just a step of rehashing, and only if there are * no...

2668

### POJ 2492 A Bug's Life

A Bug's Life Time Limit: 10000MS Memory Limit: 65536K Total Submissions:...

27910

### 聊聊storm TridentTopology的构建

storm-core-1.2.2-sources.jar!/org/apache/storm/trident/TridentTopology.java

822

1012