给你一个字符串s,找到s中最长的回文子串。
示例 1:
1 | 输入:s = "babad" |
示例 2:
1 | 输入:s = "cbbd" |
示例 3:
1 | 输入:s = "a" |
示例 4:
1 | 输入:s = "ac" |
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母(大写和/或小写)组成
重心扩展
很容易分析,回文字符串有两种,分别为长度为奇数和偶数的,但是都符合从中心扩展的特点,代码如下:
1 | func longestPalindrome(s string) string { |
分析
- 时间复杂度:O(n2),虽然时间复杂度看起来是这么多,但是内部循环首先达不到n级别,且最后的长度判断会避免很多不必要的循环,所以应该达不到O(n2)
- 空间复杂度:O(1)
Manacher 算法
详见官方解答——方法三。
但是跑下来的分数还没有上一种方法高,也是很奇怪。