如何查找字符串中最长的回文子串 三种方法详解 Ideas
如题示例
输入:s = "ababa" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
这道题主要是详细解说每一步。
一道算法题,肯定思路最先想到的肯定是暴力解法,也是最简单的,
方法一 : 暴力破解
思路:列举字符串所有的子串,判断是否为回文数,在返回其中最大的一个
(代码已经运行通过,放心食用!)
现在我来解释一下:
这个很简单,len是代表着字符串s的长度,这里就是判断一下如果s为null或者长度为1,直接返回s就是其最大回文数了。注意一下,length()是String内一个方法,返回字符串的长度,length是类的属性,返回的数组的长度。
toCharArray()方法是把字符串转化成数组,当然,我们也可以用s.charAt来读取字符,maxlen 就是最大的回文数的长度,开始肯定是1啦,begin的话就是等会我们截取回文数的起始位置。
俩个for循环目的就是列举所有的子串,i 左 j 右 ,只有当子串是回文数,且长度比maxlen(现在的最大回文数大)我们就更改一次起始位置,和maxlen。循环结束后我们就找到了最大回文数在字符串的始末位置,输出即可
substring()方法用于提取字符串中介于两个指定下标之间的字符。
这个方法就是判断 i --- j 是否为回文串。这个比较简单,写法多样,不一定要这样写。
复杂度分析:O(n*n*n) 一次遍历,俩个for循环
空间复杂度 O(1) 用到常量个临时变量。
方法二 : 动态规划
思路:一个长度大于2的回文串,将它首尾的两个字母去除之后,它仍然是个回文串。
例如对于字符串“ababa”,如果我们已经知道“bab” 是回文串,反过来,如果我们知道“bab”是字回文串,“ababa” 一定是回文串,这是因为它的首尾两个字母都是 “a”。
如果想要自己练习填写动态规划表格的话,可以在这里练习:Alchemist (alchemist-al.com)———不是本人制作,网上搜索所得。
后面还俩个 } 没有截图进来
我们还是逐句来解释
如果s小于1直接返回s
这样写也可以的
这里我们考虑的是当长度为1时,当然全都是回文串,所以全部是true
这样看是不是好理解多了?
1. maxlen是最大字符串长度,begin是等会输出最大字符串长度的起始位置,toCharArray()方法是把字符串转化成数组。
2.1 第一个 L for循环当然就是指的长度,从2开始,注意 L应该是要小于等于len的,只是小于的话,如果遇到字符串“bb”输出来的就是 “b” 而不是“bb” ,我在第一次写的是觉得长度的范围可以宽松一点,还是绝对一点比较好。第二个 for 循环当然就是左边界。
2.2 .首先表达出右边界,有了左边界和长度,我们很容易表达出来,最后要注意防止 right 超过界限,超过了就直接跳出循环,这里可以思考一下,能不能 right > len ?
3.这里是比较关键的,如果一个字符串左右俩端不相等,肯定就是不是回文串,直接false,如果相等,就看它去掉俩端的子字符串是否为回文串,是,那此字符串是回文串。注意:1.在状态转移方程中,我们是从长度较短的字符串向长度较长的字符串进行转移的,因此一定要注意动态规划的循环顺序。2.如果其长度小于2的话当然肯定一定为回文串,要小心的是我们用的索引和字符串长度的关系,我特意把它写得很仔细。
4 .这里就很简单了,满足俩个条件,一是子字符串为回文串,二是字符串长度大于之前遍历出的最大长度。和之前一样。
5.这里我还能说什么呢?还是不太明白的话请自己多去点一下大概就明白了https://alchemist-al.com/algorithms/longest-palindromic-substring
复杂度分析
时间复杂度 O(n*n) n是字符串的长度
空间复杂度O(n*n) 动态规划所需要的空间。
方法三:中心扩散 (也是此题最好的解法————我说的,不服打我脸)
思路:P(i,j) ← P(i+1,j−1) ← P(i+2,j−2) ....... 某一边界情况 , 这里我们可以发现每个状态在变化过程中都是唯一的,所以我们可以只遍历一次,每次从中心出发向俩边扩散,如果俩边字母相同,就继续扩散,不同那就停止,这样我们就找到此为中心的最大回文串,当然我们也要注意奇偶问题是不是,例如 “aba” 和 “abba“,所以我们可以每次遍历都从长度为1和长度为2分别遍历一次。枚举完所有的回文串长度后,我们就找到了最长回文串。
还是逐一解释
这个每次都出现了,我再次声明一下,这个方法有很多种 ,这种简单的小问题可以思考多种写法,看看自己能写出几种来,有人肯定觉得这看起来很傻,但是这确实能帮助我们开阔思维,最主要的是可以复习一些知识点,一些不太经常用的,或者只是了解概念的都可以用上来,只是养成一种习惯,一题想多解!
这个不明白的直接给我切腹谢罪啊!! ! 你是怎么看到这里来的 !!!
for 循环没什么好说的,要注意的 i 是小于 len - 1 的 ,为什么呢 ? 自己想!!嘿嘿,oddlen是奇数长度,even是偶数长度,最后一点需要注意的就是begin的值 , 有些读者可能不是很清晰,我放张图解释一下
哈哈哈, 是不是懂了,这都是自己可以推出来的。
这是奇偶共用的方法,找到以其为中心的最大回文串,注意的我们使用的索引,所以要减去2 ,动态规划上也如此。
好了,以上就是三种解法全部详细解释。花了我老久了,看官老爷们给个赞吧,有什么其他问题欢迎在下方评论或私聊,我都会及时的回复哟。 老爷们,这周我还有对异常处理的入门介绍,关注我快快快!!!!
上一篇: 回声字符串(验证/最长/最短/分割)
下一篇: 回声串自制脑图