有一个网站叫浪什么,腾讯云域名查询,网站备份还原,Git page wordpress给你一个字符串 s #xff0c;返回 s 中不同的非空回文子序列个数 。由于答案可能很大#xff0c;请返回对 109 7 取余 的结果。
字符串的子序列可以经由字符串删除 0 个或多个字符获得。
如果一个序列与它反转后的序列一致#xff0c;那么它是回文序列。
如果存在某个 …给你一个字符串 s 返回 s 中不同的非空回文子序列个数 。由于答案可能很大请返回对 109 7 取余 的结果。
字符串的子序列可以经由字符串删除 0 个或多个字符获得。
如果一个序列与它反转后的序列一致那么它是回文序列。
如果存在某个 i , 满足 ai ! bi 则两个序列 a1, a2, … 和 b1, b2, … 不同。
示例 1 输入s ‘bccb’ 输出6 解释6 个不同的非空回文子字符序列分别为‘b’, ‘c’, ‘bb’, ‘cc’, ‘bcb’, ‘bccb’。 注意‘bcb’ 虽然出现两次但仅计数一次。
示例 2 输入s ‘abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba’ 输出104860361 解释共有 3104860382 个不同的非空回文子序列104860361 是对 109 7 取余后的值。
提示 1 s.length 1000 s[i] 仅包含 ‘a’, ‘b’, ‘c’ 或 ‘d’
三维DP
class Solution {
public:int countPalindromicSubsequences(string s) {int MOD 1e9 7;int n s.size();vectorvectorvectorint dp(4, vectorvectorint(n, vectorint(n, 0)));for(int i 0; i n; i){dp[s[i] - a][i][i] 1; }for(int len 2; len n; len){for(int i 0, j len - 1; j n; i, j){for(char c a; c d; c){char k c - a;if(s[i] c s[j] c){dp[k][i][j] (2LL dp[0][i1][j-1] dp[1][i1][j-1] dp[2][i1][j-1] dp[3][i1][j-1]) % MOD;}else if(s[i] c){dp[k][i][j] dp[k][i][j-1];}else if(s[j] c){dp[k][i][j] dp[k][i1][j];}else{dp[k][i][j] dp[k][i1][j-1];}}}}int res 0;for(int k 0; k 4; k){res (res dp[k][0][n-1]) % MOD;}return res;}
};我们定义一个三维数组dp[k][i][j]来表示在i到j范围内并且以k开头的回文子序列的总数。我们在状态转移过程中可以先不断遍历i和j之间的范围len那么我们接下来继续遍历i的时候j实际上也会知道最后在最里层循环中遍历k是多少。
当s[I] s[j]的时候那么i1到j-1中的回文子序列加上两边的x都是以x为开头的回文子序列并且字符c可以构成c或者cc两个回文子序列所以有状态转移方程dp[k][i][j] (2LL dp[0][i1][j-1] dp[1][i1][j-1] dp[2][i1][j-1] dp[3][i1][j-1]) % MOD;。
首尾字符中只有 s[i] 是我们感兴趣的字符 c。 因此当前子串 s[i…j] 中以 c 为边界的回文子序列与子串 s[i…j-1] 中以 c 为边界的回文子序列是相同的因为 s[j] 不会对结果产生影响。
接下来的几种情况同理。
最后我们定义一个变量res来记录以不同字符开头的长度为n的字符串的回文子序列总数。
