最长回文数
给你一个字符串 s
,找到 s
中最长的回文子串。
示例 1:
1 | 输入:s = "babad" |
示例 2:
1 | 输入:s = "cbbd" |
提示:
1 <= s.length <= 1000
s
仅由数字和英文字母组成
Related Topics
- 字符串
- 动态规划
法一:暴力枚举
1 | class Solution { |
法二:中心扩散
将每”一位”作为中心向两边扩撒,
每次扩散分两种情况,
第一种情况是以当前那一位为中心向两边扩散
第二种情况是以当前那一位和下一位为中心向两边扩散
取这两种情况的最值max
如果max比maxLen大的话,计算得出begin‘
最后直接返回截取的字符串
这是我的解法
1 | class Solution { |
这是官方的解法
1 |
|
法三:动态规划
对于一个子串而言,如果它是回文串,并且长度大于 2,那么将它首尾的两个字母去除之后,它仍然是个回文串。
例如对于字符串 “ababa’”,如果我们已经知道 “bab” 是回文串这层关系,那么 “ababa” 一定是回文串,这是因为它的首尾两个字母都是a
使用dp[][]
二位数组来存储这层关系
即使用dp[i][j]
来表示s字符串的i到j是否是回文数
如果当前要判断的范围是dp[left][right]
,字符串长度为x
第一步先看首尾是否一致,
如果不一致,则dp[left][right]
直接为false,
如果一致,则进入下一步判断
如果当前判断的字符串长度小于3
为什么是3呢?
如果长度为1,则本身就是字符串,形成自回文
如果长度为2,则首尾一致的情况下,可以直接判断为回文
如果长度为3,则首尾一致的情况下,也可以直接判断回文
这三组数据是后面做判断的支撑
则直接将dp[left][right]
赋值为true
反之将dp[left+1][right-1]
(即去掉首尾的时候是否为回文数)的回文结构赋值给dp[i][j]
这些结束后,当dp[left][right]
是true时,
则将当前循环长度和存储的maxLen进行比较,
如果当前循环长度较大,则将其赋值给maxLen,将left赋值给begin
反之,直接进行下一次循环
官方代码:
1 | public class Solution { |
下面是我理解思路后写的
对于变量的命名更贴近其本身的含义
可能会更好理解一点
1 | public String longestPalindrome1(String s) { |