题目
给定一个字符串
s
,找到s
中最长的回文子串。你可以假设s
的最大长度为 1000。示例 1:
1
2
3 输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。示例 2:
1
2 输入: "cbbd"
输出: "bb"来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
关键字:回文字串,那么什么是回文字串?是正序逆序都一样的字串,也是中心对称的字串。
思考回文字串有哪些性质:
- 一定包含长度更小的回文字串
- 单个字符是回文字串,两个连续相同字符是回文子串
- 中心对称
暴力法
暴力法当然是遍历所有可能的子字符串,判断是否是回文字串,维护一个全局最大值,暴力法时间复杂度$O(N^3)$,因为每判断一个字符串的时间复杂度为$O(N)$。
改进
接下来,为了改进暴力法,我们思考暴力法中有没有重复计算的部分。我们上面已经发现了回文字串的特点:一定包含长度更小的回文字串,且一定是中心对称的,那么对每一个回文字串,它的最大回文字子串(不含自己),其前后两个字符一定是相同的。用子字符串的首尾下标表示一个子字符串是否为回文字符串:$S(b,e),~e-b>2$,那么判断它是否为回文字符串的标准为:
1 | if S(b+1,e-1) == true and S[b] == S[e]: |
可以化简为
1 | S(b,e) = S(b+1,e-1) & S[b]==S[e] |
至此我们有了递归公式,然而递归的过程中有没有重复计算呢?显然在计算更长回文字串的时候重复计算了其包含的子串,因此我们需要进行动态规划。
如此就产生了动态规划解法。
动态规划
我们需要用首尾两个变量来表示一个字符串,因此需要一个二维表来记录每个字符串是否为回文字串,空间复杂度为$O(N^2)$,时间复杂度也为$O(N^2)$,因为还是需要对所有的子字符串进行计算。
对动态规划的改进
上述动态规划是否还能改进?对每一个长度$len>2$的字符串,我们只需要判断其长度为$len-2$的中心子字符串是否是回文字符串,而不需要该子字符串的子字符串,因此为了计算长度为$len$的所有子字符串是否为回文字串,我们只需要长度为$len-2$的所有字串的判断结果。事实上,为了计算以$i$为中心($i$只表示一个位置,而不是特指一个字符,也可能是字符之间的间隙)的字符串,我们可以只用一个标志位来标志内层最长中心子字符串是否是回文字串,自下而上得到以某个位置为中心的最长回文字串,这样一来,只要我们遍历所有位置,并维持一个最长回文字串,就可以得到全局最回文字串。
这样的空间复杂度就被优化到了$O(1)$,而时间复杂度不变,因为还是遍历了所有可能子字符串。
以上思路参考了原题目官方题解,思路中比较巧妙的是为了避免区分字符串长度的奇偶带来的不便,将思考的对象由字符串本身改变为字符串中心点:因为对称,所以一定有中心点,这样大大简化了思考的难度。
实现
我们直接实现优化后的方法。步骤:
- 对每个位置:寻找以这个位置为中心的最长回文字串;
- 判断该位置为间隙还是字符
- 判断中心两侧字符是否相等(注意边界条件)
- 拓展
- 遍历$2N+1$个位置,维护最长回文子串。
代码如下:
1 | class Solution { |
但是时间和内存都爆炸了,于是我发现我的代码有如下问题:
- 没必要维护最长回文字串,只要维持最大长度及其位置就可以了;
读高赞题解的代码
先贴代码再分析思路:
1 | class Solution { |
- 首先是中心拓展的辅助函数,接收字符串以及拓展的起点,返回回文字串最大长度;
- 然后在主函数中维护最大长度以及首尾位置;
- 遍历字符串,以每个位置为中心计算最长回文子串,维护最大回文子串位置;
马拉车算法代码
1 | class Solution { |