JAVA程序设计:统计不同回文子字符串(LeetCode:730)

2024-06-02 15:38

本文主要是介绍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)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1024383

相关文章

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Spring Cloud之注册中心Nacos的使用详解

《SpringCloud之注册中心Nacos的使用详解》本文介绍SpringCloudAlibaba中的Nacos组件,对比了Nacos与Eureka的区别,展示了如何在项目中引入SpringClo... 目录Naacos服务注册/服务发现引⼊Spring Cloud Alibaba依赖引入Naco编程s依

java导出pdf文件的详细实现方法

《java导出pdf文件的详细实现方法》:本文主要介绍java导出pdf文件的详细实现方法,包括制作模板、获取中文字体文件、实现后端服务以及前端发起请求并生成下载链接,需要的朋友可以参考下... 目录使用注意点包含内容1、制作pdf模板2、获取pdf导出中文需要的文件3、实现4、前端发起请求并生成下载链接使

Java springBoot初步使用websocket的代码示例

《JavaspringBoot初步使用websocket的代码示例》:本文主要介绍JavaspringBoot初步使用websocket的相关资料,WebSocket是一种实现实时双向通信的协... 目录一、什么是websocket二、依赖坐标地址1.springBoot父级依赖2.springBoot依赖

如何用java对接微信小程序下单后的发货接口

《如何用java对接微信小程序下单后的发货接口》:本文主要介绍在微信小程序后台实现发货通知的步骤,包括获取Access_token、使用RestTemplate调用发货接口、处理AccessTok... 目录配置参数 调用代码获取Access_token调用发货的接口类注意点总结配置参数 首先需要获取Ac

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字