算法43:动态规划专练(最长回文子串 力扣5题)---范围模型

2024-03-04 04:36

本文主要是介绍算法43:动态规划专练(最长回文子串 力扣5题)---范围模型,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

之前写过一篇最长回文子序列的博客算法27:最长回文子序列长度(力扣516题)——样本模型 + 范围模型-CSDN博客

在那一篇博客中,回文是可以删除某些字符串组成的。比如:

字符串为:a1b3c4fdcdba, 那么最长回文子序列就是 abccba。长度为6。

本题为力扣第5题:最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

解释一下,如果字符串为 abc121dmcba. 那么最长回文子序列为 abc121cba. 而最长回文子串则为:121.  子串必须是连续的。

一眼看上去就是范围模型。而范围模型就是要讨论样本数据的开头和结尾的情况:

1. 如果字符串为空,那么回文为空字符

2. 如果字符长度为1, 回文子串就为字符串本身

3. 如果字符串长度2, 则字符串下标0和1的字符进行比较,相等则为字符串本身;不等的话,返回其中一个字符即可。这是我在提交代码的时候,力扣提示错误的时候发现的。

为什么要单独讨论长度为 1 和 2 的情况?

因为, 范围模型讨论数据的开头和结尾。如果原始字符串长度为2,则直接走上方的3逻辑; 可如果一个很长的字符串,经过不断的递归以后,最终长度为2的时候,这就比较麻烦了。

比如 *******ab****的时候,你就不能随意返回一个字符作为回文了。

如果你返回a, 那么字符串为mnfabbbbbbbbb. 那你肯定是错误的

如果你返回b,那么字符串为mnfaaaaaaaaabb, 那你肯定也是错的。

回文,就是整体与子串的关系

其实,最长回文子串,最难的就是连续子串的判断。

012345
acddck

字符串为 acddck, 下标1和下标4相等,都为c.  如果下标从1到4 是回文。 那么他的子串

下标2到3也必须是回文才行。这才是判断的核心点。 而下方的推导表格,完全符合。

比如这个字符串为abdddfm。那么二维表格为:

我用x代表空字符串

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)aX
b (1)bX
d (2)ddd
d (3)ddd
d (4)dX
f (5)fX
m (6)m

由下往上,由左往右推算:

我用x代表空字符串

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)aXd 类推 类推 类推 类推
b (1)bX   类推 类推 类推
d (2)ddd

 

 前dd,

左下d,

下为dd

当前下标与下标2的字符相等。下标 2到4的子串为 3到3。 而3行3列是回文并且回文为d。

那么 d + d + d = ddd

 类推 类推
d (3)ddd

 前dd,

左下d,

下为空字符

f不等于下标3的d。

取最长的 dd

 类推
d (4)dXX
f (5)fX
m (6)m

最终的二维表就是

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)aXbddddddddddd
b (1)bXddddddddddd
d (2)dddddddddddd
d (3)ddddddd
d (4)dXX
f (5)fX
m (6)m

直观的看,最长回文字符就是 ddd.

下面贴出递归代码:

package code04.动态规划专项训练03;/*** 力扣 5 题 : 最长回文子串* https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming*/
public class LongestPalindrome_01 {public String longestPalindrome(String s) {if (s == null || s.isEmpty()) {return "";}if (s.length() == 1) {return s;}if (s.length() ==  2) {return s.charAt(0) == s.charAt(1) ? s : String.valueOf(s.charAt(0));}char[] ss = s.toCharArray();return help(ss, 0, ss.length -1);}//样本对应模型: 就是从后往前讨论样本数据的末尾下标无限可能。此处的末尾下标应该为0;public String help(char[] ss, int index1,  int index2){//只有一个字符if (index1 == index2) {return  String.valueOf(ss[index1]);}//两个字符if (index1 == index2 - 1) {String temp = "";if (ss[index1] == ss[index2]) {temp = String.valueOf(ss[index1]) + String.valueOf(ss[index2]);}return temp;}//index2不作为结尾,index作为开头String p1 = help(ss, index1, index2 - 1);//index2作为结尾,index1不作为开头String p2 = help(ss, index1 + 1, index2);//index2不作为结尾,index1 不作为开头String p3 = help(ss, index1 + 1, index2 - 1);//index2作为结尾, index1 作为开头String p4 = ss[index1] == ss[index2] ? help(ss, index1 + 1, index2 - 1) : "";if (!"".equals(p4) && (index2 - index1 - 1) == p4.length()) {p4 =  String.valueOf(ss[index1]) + p4 + String.valueOf(ss[index2]);}String result =  p1.length() > p2.length() ? p1 : p2;result = result.length() > p3.length() ? result : p3;result = result.length() > p4.length() ? result : p4;return result;}public static void main(String[] args) {//String s= "bab";//String s= "babad";//String s = "ac";//String s= "cbbd";//String s= "abdka";String s= "aacabdkacaa";LongestPalindrome_01 ss = new LongestPalindrome_01();System.out.println(ss.longestPalindrome(s));}
}

动态规划:

package code04.动态规划专项训练03;/*** 力扣 5 题 : 最长回文子串* https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming*/
public class LongestPalindrome_01_opt {public String longestPalindrome(String s) {if (s == null || s.isEmpty()) {return "";}if (s.length() == 1) {return s;}if (s.length() == 2) {return s.charAt(0) == s.charAt(1) ? s : s.substring(0,1);}char[] ss = s.toCharArray();int size = ss.length;//二维动态规划表,列数多构建1String[][] dp = new String[size][size];//构建dp的斜线for (int i = 0; i < s.length() - 1; i++) {//只构建斜线上方部分. 由递归的if (index1 == index2) 得到dp[i][i] = String.valueOf(ss[i]);//由递归的if (index1 == index2 - 1)得到。递归中还特出判断了length == 2 即原始数组长度为2的//情况。但是,动态规划中原始数组长度为2在上方代码已经判断过了。因此,此处只需要关注通用逻辑即可dp[i][i+1] =  ss[i] == ss[i + 1] ? String.valueOf(ss[i]) + String.valueOf(ss[i+1]) : "";}//最后一行最后一列比较特殊,会出现数组越界,因此单独构造dp[size - 1][size - 1] = String.valueOf(ss[size - 1]);//行,从倒数第3行开始,由下放上推; 因为倒数第1、2行上方代码已经推算出来了for (int index1 = size - 3; index1 >= 0; index1--) {//列,由左往右推。 这个地方的 index2 = index1 + 2需要看图理解for (int index2 = index1 + 2; index2 < size; index2++) {//index2不作为结尾,index作为开头String p1 = dp[index1][index2 - 1];//index2作为结尾,index1不作为开头String p2 = dp[index1 + 1][index2];//index2不作为结尾,index1 不作为开头String p3 = dp[index1 + 1][index2 - 1] != null ? dp[index1 + 1][index2 - 1] : "";//index2作为结尾, index1 作为开头String p4 = ss[index1] == ss[index2] ? dp[index1 + 1][index2 - 1] : "";//特殊处理一下p4为null的情况p4 = p4 == null ? "" : p4;if (!"".equals(p4) && (index2 - index1 - 1) == p4.length()) {p4 =  String.valueOf(ss[index1]) + p4 + String.valueOf(ss[index2]);}String result =  p1.length() > p2.length() ? p1 : p2;result = result.length() > p3.length() ? result : p3;result = result.length() > p4.length() ? result : p4;dp[index1][index2] = result;}}return dp[0][size -1];}public static void main(String[] args) {//String s= "bab";//String s= "babad";//String s = "ac";//String s= "cbbd";//String s= "abdka";String s= "aacabdkacaa";//String s= "abbcccbbbcaaccbababcbcabca";LongestPalindrome_01_opt ss = new LongestPalindrome_01_opt();System.out.println(ss.longestPalindrome(s));}
}

测试结果:

测试结果很不理想。速度慢,而且还吃内存,吃内存的主要原因就是动态规划的二维表是字符串类型的。

看了看力扣官方的思想,确实相当不错。下面直接说一下官方的解题思路

1. 官方并不存储字符串,而是存一个flag,标记回文范围.

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)truefalse
b (1)truefalse
d (2)truetrue
d (3)truetrue
d (4)truefalse
f (5)truefalse
m (6)true

力扣官方定义了一个最长回文子串的开始位置,beginIndex,长度length

从倒数第3行开始,依旧是由下往上,由左往右推算

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)truefalsefalsefalsefalsefalsefalse
b (1)truefalsefalsefalsefalsefalse
d (2)truetrue

d == d,并且

子串 3行3列也是回文

整体是回文。

开始位置为2,

长度为3

falsefalse
d (3)truetrue

d != f

false

m != d

false

d (4)truefalse

d != m

false

f (5)truefalse
m (6)true

最后,就是根据上方的推算结果进行字符串截图。知道了开始位置,截取字符的长度,问题自然就解决了。

代码如下:

package code04.动态规划专项训练03;/*** 力扣 5 题 : 最长回文子串* https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming*/
public class LongestPalindrome_01_opt2_1 {public String longestPalindrome(String s) {if (s == null || s.isEmpty()) {return "";}if (s.length() == 1) {return s;}if (s.length() == 2) {return s.charAt(0) == s.charAt(1) ? s : s.substring(0,1);}char[] ss = s.toCharArray();int size = ss.length;//默认开始下标为最后一行的最后一列int beginIndex = size -1;//默认回文长度为1int length = 1;//二维动态规划表,列数多构建1boolean[][] dp = new boolean[size][size];//构建dp的斜线for (int i = 0; i < s.length(); i++) {//只构建斜线上方部分. 由递归的if (index1 == index2) 得到dp[i][i] = true;}//行,从倒数第2行开始,由下放上推; 因为倒数第1行上方代码已经推算出来了for (int index1 = size - 2; index1 >= 0; index1--) {//列,由左往右推。 当前行的剩余列for (int index2 = index1 + 1; index2 < size; index2++) {//长度为2. 开头、结尾相等就是回文if (index1 == index2 - 1) {//开头、结尾相等。那么 [index1, index2] 就是回文dp[index1][index2] =  ss[index1] == ss[index2] ? true : false;}else {dp[index1][index2] =  ss[index1] == ss[index2] ? dp[index1 + 1][index2 -1] : false;}// [index1, index2] 的个数就是 index2 - index1 + 1;if( dp[index1][index2] && index2 - index1 + 1 > length) {beginIndex = index1;length = index2 - index1 + 1;}}}return s.substring(beginIndex, beginIndex + length);}public static void main(String[] args) {//String s= "bab";//String s= "babad";//String s = "ac";String s= "cbbd";//String s= "abdka";//String s= "aacabdkacaa";//String s= "abbcccbbbcaaccbababcbcabca";LongestPalindrome_01_opt2_1 ss = new LongestPalindrome_01_opt2_1();System.out.println(ss.longestPalindrome(s));}
}

这篇关于算法43:动态规划专练(最长回文子串 力扣5题)---范围模型的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Spring Security基于数据库的ABAC属性权限模型实战开发教程

《SpringSecurity基于数据库的ABAC属性权限模型实战开发教程》:本文主要介绍SpringSecurity基于数据库的ABAC属性权限模型实战开发教程,本文给大家介绍的非常详细,对大... 目录1. 前言2. 权限决策依据RBACABAC综合对比3. 数据库表结构说明4. 实战开始5. MyBA

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.