统计不同回文子字符串--LeetCode730:分析清晰

2024-06-02 15:38

本文主要是介绍统计不同回文子字符串--LeetCode730:分析清晰,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

统计不同回文子字符串–LeetCode730

题目

给定一个字符串 S,找出 S 中不同的非空回文子序列个数,并返回该数字与 10^9 + 7的模。通过从 S 中删除 0 个或多个字符来获得子字符序列。如果一个字符序列与它反转后的字符序列一致,那么它是回文字符序列。如果对于某个 iA_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[i][j]表示s[i, j]中回文子序列的个数。

转移方程:

  • 如果s[i] != s[j],则有dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]dp[i + 1][j - 1]dp[i][j - 1]dp[i+1][j]中都有,所以要减去一个。
  • 如果s[i] = s[j] = c,则有dp[i][j] = 2 * dp[i + 1][j - 1],乘以2意思是在s[i + 1, j - 1]中所有的回文子序列两边加上c,就构成了新的回文子序列,原来有dp[i + 1][j - 1]这么多个,两边加上c之后增加了dp[i + 1][j - 1]个回文子序列,所以乘以2得到当前的dp[i][j]

但是上述s[i] = s[j]情况下,结果存在重复计算和疏漏,需要进行去重和补充。

  • 如果在s[i + 1, j - 1]没有字符c,需要进行补充,即dp[i][j] += 2,补上的是[c], [c, c];
  • 如果在s[i + 1, j - 1]只有一个字符c,需要进行补充,即dp[i][j] += 1,补上的是[c, c];
  • 如果在s[i + 1, j - 1]有两个或多个字符c,需要进行去重,即dp[i][j] -= dp[l + 1][r - 1]li的左边第一个字符为c的位置, rj的右边第一个字符为c的位置。

初始条件:

  • dp[n - 1][n - 1] = 1表示单个字符就是一个回文子序列
  • dp[i][i - 1] = 0表示字符串为空

最终答案就是dp[0][n-1]

参考题解:
阿飞的题解
想想大司马会怎么做的题解

代码如下(用时69ms):

class Solution {public int countPalindromicSubsequences(String S) {if (S == null || S.length() == 0) {return 0;}int n = S.length();int mod = 1000000000+7;int[][] dp = new int[n][n];for (int i = 0; i < n; i++) {dp[i][i] = 1;}for (int i = n-2; i >= 0; i--) {for (int j = i+1; j < n; j++) {if (S.charAt(i) == S.charAt(j)) {dp[i][j] = 2*dp[i+1][j-1];int left = i+1;int right = j-1;while (left <= right && S.charAt(i) != S.charAt(left)) left++;while (left <= right && S.charAt(j) != S.charAt(right)) right--;if (left > right) {dp[i][j] += 2;} else if (left == right) {dp[i][j] += 1;} else {dp[i][j] -= dp[left+1][right-1];}}else {dp[i][j] = dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];}dp[i][j] = (dp[i][j] < 0) ? dp[i][j]+mod : dp[i][j]%mod;}}return dp[0][n-1];}
}

这篇关于统计不同回文子字符串--LeetCode730:分析清晰的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot中六种批量更新Mysql的方式效率对比分析

《SpringBoot中六种批量更新Mysql的方式效率对比分析》文章比较了MySQL大数据量批量更新的多种方法,指出REPLACEINTO和ONDUPLICATEKEY效率最高但存在数据风险,MyB... 目录效率比较测试结构数据库初始化测试数据批量修改方案第一种 for第二种 case when第三种

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

MySQL中的LENGTH()函数用法详解与实例分析

《MySQL中的LENGTH()函数用法详解与实例分析》MySQLLENGTH()函数用于计算字符串的字节长度,区别于CHAR_LENGTH()的字符长度,适用于多字节字符集(如UTF-8)的数据验证... 目录1. LENGTH()函数的基本语法2. LENGTH()函数的返回值2.1 示例1:计算字符串

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理;Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令