本次题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
// 输入: "babad"
// 输出: "bab"
// 注意: "aba" 也是一个有效答案。
示例 2:
// 输入: "cbbd"
// 输出: "bb"
解题思路
解法1 - 中心拓展法
由于回文字符串的对称性，所以每次可以选择一个数字作为中心，进行左右拓展来判断是否是回文串。
由于字符串有可能为奇数，有可能为偶数，所以需要从 1 or 2个字符之间开始拓展。
意思就是有 i + i - 1个拓展中心。
则 i 为奇数位，
i + 1为偶数位。
以此为理论依据每次循环往两边拓展即可。
此解法时间复杂度是O(n^2)。
空间复杂度是O(1)。
解法2 - 马拉车算法
第一次接触这个算法，但是想出这个算法的人，确实牛逼。
马拉车算法将时间复杂度提升到了线性。
此算法最初遍历字符，在每个字符两边都插入一个特殊符号，为避免越界，首尾加上特殊标签，例如：
aabbcbbaa -> ^#a#a#b#b#c#b#b#a#a#$
保证当前字符串一定为奇数。
然后左右扩展。
利用一个长度为原字符串长度的数组arr来保存中心扩展的最大个数。
(arr每个元素的下标 - arr[i]) / 2 就是原字符串的字符的下标。
我们设C为字符串中心，R为字符串右边的长度，则有R = C + arr[i]。
这时候就可以用中心扩展法去求。
我们用j表示第i个字符与C对应的下标。
但有以下三种情况会导致arr[j]不正确
- 长度超出了R
- arr[j]到了原字符串的左边界
- 当i就是为R时
所以遇到以上三种情况，我们需要利用中心拓展法去做边界处理。
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
软考中级精品资料免费领
历年真题答案解析
备考技巧名师总结
高频考点精准押题
- 资料下载
- 历年真题
193.9 KB下载数265
191.63 KB下载数245
143.91 KB下载数1148
183.71 KB下载数642
644.84 KB下载数2756
