730. 统计不同回文子序列https://leetcode.cn/problems/count-different-palindromic-subsequences/
难度困难231
给定一个字符串 s,返回 s
中不同的非空「回文子序列」个数 。
通过从 s 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致,那么它是「回文字符序列」。
如果有某个 i
, 满足 ai != bi
,则两个序列 a1, a2, ...
和 b1, b2, ...
不同。
注意:
- 结果可能很大,你需要对
109 + 7
取模 。
示例 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'
通过次数9,375提交次数15,597
请问您在哪类招聘中遇到此题?
class Solution {
public int countPalindromicSubsequences(String s) {
final int MOD = 1000000007;
int n = s.length(); // 字符串的长度
int[][][] dp = new int[4][n][n]; //4是因为s中只包含4个字符
//初始化
for(int i=0;i<n;i++) dp[s.charAt(i)-'a'][i][i]=1; //字符区间在[i:i]之间并且以字符x开头和结尾的回文序列数量为1、
for(int len=2;len<=n;len++)
{
for(int i=0;i+len<=n;i++)
{
int j=i+len-1;
for(char c='a';c<='d';c++)
{
int k=c-'a';
if(s.charAt(i)==c && s.charAt(j)==c)
dp[k][i][j] = (2 + (dp[0][i + 1][j - 1] + dp[1][i + 1][j - 1]) % MOD + (dp[2][i + 1][j - 1] + dp[3][i + 1][j - 1]) % MOD) % MOD;
else if(s.charAt(i)==c) dp[k][i][j] = dp[k][i][j-1];
else if(s.charAt(j)==c) dp[k][i][j] = dp[k][i+1][j];
else dp[k][i][j] = dp[k][i+1][j-1];
}
}
}
int res = 0;
for(int i=0;i<4;i++)
res = (res+dp[i][0][n-1]) % MOD;
return res;
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/69060.html