LeetCode 5. 最长回文子串
题目描述
思路分析
中心扩展法
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func longestPalindrome(s string) string {
n := len(s)
res := ""
expandAroundCenter := func(left, right int) (int, int) {
for left >= 0 && right < n && s[left] == s[right] {
left--
right++
}
// 当不再满足回文时，真实回文子串为 s[left+1:right]
return left + 1, right
}
for i := 0; i < n; i++ {
// 奇数长度回文，中心在 i
start1, end1 := expandAroundCenter(i, i)
// 偶数长度回文，中心在 i 和 i+1 之间
start2, end2 := expandAroundCenter(i, i+1)
// 更新 res，如果找到更长的回文
if end1-start1 > len(res) {
res = s[start1:end1]
}
if end2-start2 > len(res) {
res = s[start2:end2]
}
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func longestPalindrome(s string) string {
res := ""
for i := 0; i < len(s); i++ {
s1 := expandAroundCenter(s, i, i)
s2 := expandAroundCenter(s, i, i+1)
if len(s1) > len(res) {
res = s1
}
if len(s2) > len(res) {
res = s2
}
}
return res
}
func expandAroundCenter(s string, i, j int) string {
for i >= 0 && j < len(s) && s[i] == s[j] {
i--
j++
}
return s[i+1 : j]
}
- 时间复杂度：
O(n^2)。每个字符都作为中心进行扩展。- 空间复杂度：
O(1)。只用了常数空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！