Java实现 LeetCode 730 统计不同回文子字符串(动态规划)

2024-06-02 15:38

本文主要是介绍Java实现 LeetCode 730 统计不同回文子字符串(动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

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’} 中的某一个。

PS:
因为只有四种字符,dp的第一位是哪几种字符,第二个是字符串的一个索引,第三个是字符串的第二个索引

class Solution {public int countPalindromicSubsequences(String S) {int n = S.length();int mod = 1000000007;int[][][] dp = new int[4][n][n];for (int i = n-1; i >= 0; --i) {for (int j = i; j < n; ++j) {for (int k = 0; k < 4; ++k) {char c = (char) ('a' + k);if (j == i) {if (S.charAt(i) == c) dp[k][i][j] = 1;else dp[k][i][j] = 0;} else { // j > i i是倒着循环的所有是i+1(上一个)if (S.charAt(i) != c) dp[k][i][j] = dp[k][i+1][j];//          j是正着循环的,所以是j-1else if (S.charAt(j) != c) dp[k][i][j] = dp[k][i][j-1];else { // S[i] == S[j] == c//如果是两个的话,就是两种i+1和jif (j == i+1) dp[k][i][j] = 2; // "aa" : {"a", "aa"}else { // length is > 2dp[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;}}}}}}}int ans = 0;for (int k = 0; k < 4; ++k) {ans += dp[k][0][n-1];ans %= mod;}return ans;} 
}

PS:
大佬的二维数组的代码

class Solution {int[][] memo, prv, nxt;byte[] A;int MOD = 1_000_000_007;public int countPalindromicSubsequences(String S) {int N = S.length();prv = new int[N][4];nxt = new int[N][4];memo = new int[N][N];for (int[] row: prv) Arrays.fill(row, -1);for (int[] row: nxt) Arrays.fill(row, -1);A = new byte[N];int ix = 0;for (char c: S.toCharArray()) {A[ix++] = (byte) (c - 'a');}int[] last = new int[4];Arrays.fill(last, -1);//前i位离i最近的位置(含有相同的字符)for (int i = 0; i < N; ++i) {last[A[i]] = i;for (int k = 0; k < 4; ++k)prv[i][k] = last[k];}//同理 Arrays.fill(last, -1);for (int i = N-1; i >= 0; --i) {last[A[i]] = i;for (int k = 0; k < 4; ++k)nxt[i][k] = last[k];}return dp(0, N-1) - 1;}//记忆化搜索public int dp(int i, int j) {if (memo[i][j] > 0) return memo[i][j];int ans = 1;if (i <= j) {for (int k = 0; k < 4; ++k) {int i0 = nxt[i][k];int j0 = prv[j][k];//后i位的有相同字符的最近索引大于等于当前索引,自己可以算一个if (i <= i0 && i0 <= j) ans++;//k字符出现过,并且后面也出现过if (-1 < i0 && i0 < j0) ans += dp(i0 + 1, j0 - 1);if (ans >= MOD) ans -= MOD;}}memo[i][j] = ans;return ans;}}

这篇关于Java实现 LeetCode 730 统计不同回文子字符串(动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

Qt把文件夹从A移动到B的实现示例

《Qt把文件夹从A移动到B的实现示例》本文主要介绍了Qt把文件夹从A移动到B的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录如何移动一个文件? 如何移动文件夹(包含里面的全部内容):如何删除文件夹:QT 文件复制,移动(

Flask 验证码自动生成的实现示例

《Flask验证码自动生成的实现示例》本文主要介绍了Flask验证码自动生成的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习... 目录生成图片以及结果处理验证码蓝图html页面展示想必验证码大家都有所了解,但是可以自己定义图片验证码

VSCode配置Anaconda Python环境的实现

《VSCode配置AnacondaPython环境的实现》VisualStudioCode中可以使用Anaconda环境进行Python开发,本文主要介绍了VSCode配置AnacondaPytho... 目录前言一、安装 Visual Studio Code 和 Anaconda二、创建或激活 conda

使用mvn deploy命令上传jar包的实现

《使用mvndeploy命令上传jar包的实现》本文介绍了使用mvndeploy:deploy-file命令将本地仓库中的JAR包重新发布到Maven私服,文中通过示例代码介绍的非常详细,对大家的学... 目录一、背景二、环境三、配置nexus上传账号四、执行deploy命令上传包1. 首先需要把本地仓中要

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

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

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名,员

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、前端发起请求并生成下载链接使