统计不同回文子序列
统计不同回文子序列
给定一个字符串 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'
解题思路：
1，对于子区间[i,j],我们分别计算以x开头的回文子串的数量为dp[x,i,j]
2,分四种情况
A，s[i]=s[j]=x，这个时候有
dp[x,i,j]=sum(dp[k,i+1,j-1])+2；其中2是两个特殊子串 x和xx
B,s[i]=x
dp[x,i,j]=dp[x,i,j-1]
C,s[j]=x
dp[x,i,j]=dp[x,i+1,j]
D,s[i],s[j]和x都不相等
dp[x,i,j]=dp[x,i+1,j-1]
3,由于i依赖i+1，j依赖j-1；所以i递增，j递减
4,初始化条件
i=j dp[x][i][j]=1
i>j dp[x][i][j]=0
代码实现
func countPalindromicSubsequences(s string) int {
var dp [4][][]int
n:=len(s)
for x:=0;x<4;x++{
dp[x]=make([][]int,n)
for i:=0;i<n;i++{
dp[x][i]=make([]int,n)
}
}
mod:=int(1e9+7)
for i,r:=range s{
dp[int(r-'a')][i][i]=1
}
for i:=n-1;i>=0;i--{
for j:=i+1;j<n;j++{
for x:=0;x<4;x++{
if s[i]==s[j]&&x==int(s[i]-'a'){
for k:=0;k<4;k++{
dp[x][i][j]+=dp[k][i+1][j-1]
dp[x][i][j]=dp[x][i][j]% mod
}
dp[x][i][j]+=2
dp[x][i][j]=dp[x][i][j]% mod
}else if int(s[i]-'a')==x{
dp[x][i][j]= dp[x][i][j-1]
}else if int(s[j]-'a')==x{
dp[x][i][j]= dp[x][i+1][j]
}else{
dp[x][i][j]= dp[x][i+1][j-1]
}
}
}
}
res:=0
for x:=0;x<4;x++{
res=(res+dp[x][0][n-1])%mod
}
return res
}本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！