最长回文子串:动态规划推导

2024-08-29 23:44

本文主要是介绍最长回文子串:动态规划推导,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最长回文子串:结合图形推导动态规划

题目介绍

本题可以在力扣找到,题号为5。
给你一个字符串 s,找到 s 中最长的 回文子串。

示例 1:

输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:

输入:s = “cbbd”
输出:“bb”

提示:

1 <= s.length <= 1000
s 仅由数字和英文字母组成

暴力解法

先从暴力解法入手,对于长度为n的字符串,总共有 (n+1) * n / 2 种组合,我们可以找出每种组合,然后判断其是否是回文串,最后与当前的最大值进行比较,若新串更大,就更新答案。

我们先写一个判断回文串的函数,用双指针判断即可:

    public static boolean isPalindrome(String s) {int left = 0;int right = s.length() - 1;while (left < right) {if (s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}

然后我们用双重循环,遍历到每一种可能,在进行进一步判断:

class Solution {public String longestPalindrome(String s) {String resp = "";int ans = 0;int[][] dp = new int[s.length()][s.length()];int n = s.length();for (int i = 0;i < n;i++) {for (int j = i;j < n;j++) {//获取子串String subString = s.substring(i,j+1);//判断是否要更新最长子串if (subString.length() > resp.length() && isPalindrome(subString)) {resp = subString;}}}//返回答案return resp;}public boolean isPalindrome(String s) {int left = 0;int right = s.length() - 1;while (left < right) {if (s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}
}

动态规划

接下来我们可以考虑动态规划的解法,所谓动态规划,就是用之前的状态递推后面的状态。首先我们需要确定一个状态转移条件,对于一个 字符串 来说,如果有 一个子串str 为回文串,且 str的前一个字符和后一个字符也相同(比如说 “aba” 和 “aabaa”)那么就说明 [str-1,str+1] 也为回文串。我们可以定一个二维数组,将其定义为 从 i 到 j 的子串是否是回文串:

//初始化一个状态数组--布尔类型
int[][] dp = new int[n][n];
for (int i = 0;i < n;i++) {//对于单个字符的情况,必定为回文串dp[i][i] = true;
}

根据我们之前的结论,可以推出状态转移方程,即

if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == true) {dp[i][j] = true;
} else {dp[i][j] = false;
}

可以看到,dp[i][j]的状态是基于 dp[i+1][j-1]的,即若要得到 dp[i][j],则要先得到dp[i+1][j-1]的状态,光这么描述其实还是很抽象,我们借助矩阵图来理解:
在这里插入图片描述
我们把横轴作为j,纵轴作为i,首先我们可以填充 dp[i][i],即只有一个字符的情况,都可以填充为true:
在这里插入图片描述
其次,对于j > i 的情况其实都可以不用考虑,因为起始位置是要始终小于结束位置的:
在这里插入图片描述
接着,我们推到一般情况的依赖关系,我们先任选一点,比如 dp[0][2],根据状态转移方程,我们需要参考的就是 dp[1][1] 的状态值了:
在这里插入图片描述
即,对于每一个状态,在二位图像上总是需要依赖其左下角的具体状态,所以理论上来说,只要从对线向右上填充,我们就可以得到整个dp数组的状态了:
在这里插入图片描述
对于上面的示例来说,只要我们填充了 i = j 以及 i + 1 = j 这两条对角线,我们就可以成功推导出整个dp数组的状态,接下来我们开始编程实现:

    public static String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];//填充对角线for (int i = 0;i < n;i++) {dp[i][i] = true;}//填充 j = i + 1for (int i = 0;i < n-1;i++) {int j = i + 1;if (s.charAt(i) == s.charAt(j)) {dp[i][j] = true;}}//填充其余情况,按对角线顺序填充for (int offset = 0;offset < n-2;offset++) {for (int i = 0;i < n-2-offset;i++) {int j = i + 2 + offset;if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {dp[i][j] = true;}}}//遍历dp数组,求出最长值int longestLength = 0;String resp = "";for (int i = 0;i < n;i++) {for (int j = 0;j < n;j++) {if (dp[i][j] && j - i + 1 > longestLength) {longestLength = j - i + 1;resp = s.substring(i,j+1);}}}return resp;}

具体实现就如上,需要注意的是,由于 dp[i][j] 依赖于 dp[i+1][j-1],即依赖于左下角的状态,所以我们填充一般状态的时候也需要按照这个顺序填充,即需要按照对角线层层填充才能得到正确答案。

我们可以与暴力做法的耗时作比较,暴力解法耗时大概在 1000ms左右,而上面这种基于动态规划的解法耗时只有 200ms左右:
在这里插入图片描述
大幅优化了耗时,不过上述解法中还有可以改进的地方,比如我们可以在填充dp数组的时候就开始寻找答案,而不是分两步走:

    public static String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];//填充对角线for (int i = 0;i < n;i++) {dp[i][i] = true;}int longestLength = 1;String resp = s.charAt(0) + "";//填充 j = i + 1for (int i = 0;i < n-1;i++) {int j = i + 1;if (s.charAt(i) == s.charAt(j)) {dp[i][j] = true;if (j - i + 1 > longestLength) {longestLength = j - i + 1;resp = s.substring(i,j+1);}}}//填充其余情况,按对角线顺序填充for (int offset = 0;offset < n-2;offset++) {for (int i = 0;i < n-2-offset;i++) {int j = i + 2 + offset;if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {dp[i][j] = true;//将判断步骤放入填充步骤中if (j - i + 1 > longestLength) {longestLength = j - i + 1;resp = s.substring(i,j+1);}}}}return resp;}

这样我们就可以省去一次遍历的开销,最终优化效果到 139ms 左右:
在这里插入图片描述

这篇关于最长回文子串:动态规划推导的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl