本文主要是介绍JAVA程序设计：统计不同回文子字符串（LeetCode：730），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。
通过从 S 中删除 0 个或多个字符来获得子字符序列。
如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。
如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。
示例 1：
输入：
S = 'bccb'
输出：6
解释：
6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。
示例 2：
输入：
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：
共有 3104860382 个不同的非空回文子字符序列，对 10^9 + 7 取模为 104860361。
提示：
字符串 S 的长度将在[1, 1000]范围内。
每个字符 S[i] 将会是集合 {'a', 'b', 'c', 'd'} 中的某一个。
方法一：动态规划（三维数组实现）
我们设dp[x][i][j] 为子串 S[i...j] 拥有不同回文子字符串的答案，其中x为0到3表示子序列以四种字符的某一种结尾的方案数。
class Solution {private int mod=1000000007;public int countPalindromicSubsequences(String S) {int ans=0;int len=S.length();int[][][] dp=new int[4][len][len];for(int i=len-1;i>=0;i--)for(int j=i;j<len;j++)for(int k=0;k<4;k++) {char c=(char)('a'+k);if(i==j) {if(S.charAt(i)==c) dp[k][i][j]=1;else dp[k][i][j]=0;}else {if(S.charAt(i)!=c) dp[k][i][j]=dp[k][i+1][j];else if(S.charAt(j)!=c) dp[k][i][j]=dp[k][i][j-1];else {if(j==i+1) dp[k][i][j]=2;else {dp[k][i][j]=2;for(int m=0;m<4;m++) {dp[k][i][j]+=dp[m][i+1][j-1];dp[k][i][j]%=mod;}}}}}for(int i=0;i<4;i++)ans=(ans+dp[i][0][len-1])%mod;return ans;}
}
方法二：动态规划（二维数组实现）
在上一个方法的基础上进行空间的简化，因为我们完全没有必要多开一维存储回文串左右端点的字符，因为回文串的情况无非是单独的a,b,c,d,或者a....a,b....b,c....c,d....d这样的形式，我们直接计数就好啦。
class Solution {int[] p,last;int[][] memo,pre,nxt;private int mod=1000000007;public int countPalindromicSubsequences(String S) {int len=S.length();last=new int[4];p=new int[len];pre=new int[len][4];nxt=new int[len][4];memo=new int[len][len];for(int i=0;i<len;i++) {for(int j=0;j<4;j++) {pre[i][j]=-1;nxt[i][j]=-1;}p[i]=(int)(S.charAt(i)-'a');}for(int i=0;i<4;i++) last[i]=-1;for(int i=0;i<len;i++) {last[p[i]]=i;for(int j=0;j<4;j++)pre[i][j]=last[j];}for(int i=0;i<4;i++) last[i]=-1;for(int i=len-1;i>=0;i--) {last[p[i]]=i;for(int j=0;j<4;j++)nxt[i][j]=last[j];}return dp(0,len-1)-1;}private int dp(int l,int r) {if(memo[l][r]>0) return memo[l][r];int ans=1;if(l<=r) {for(int k=0;k<4;k++) {int p1=nxt[l][k];int p2=pre[r][k];if(l<=p1 && p1<=r) ans++;if(-1<p1 && p1<p2) ans+=dp(p1+1,p2-1);if(ans>=mod) ans-=mod;}}memo[l][r]=ans;return ans;}
}
这篇关于JAVA程序设计：统计不同回文子字符串（LeetCode：730）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
