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
func longestPalindrome(s string) string {
if len(s) < 1 {
return ""
}
start, end := 0, 0
for i := 0; i < len(s); i++ {
len1 := expandAroundCenter(s, i, i) // 奇数长度
len2 := expandAroundCenter(s, i, i+1) // 偶数长度
maxLen := max(len1, len2)
if maxLen > end-start {
start = i - (maxLen-1)/2
end = i + maxLen/2
}
}
return s[start : end+1]
}
func expandAroundCenter(s string, left int, right int) int {
for left >= 0 && right < len(s) && s[left] == s[right] {
left--
right++
}
return right - left - 1
}
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 := palindrome(s, i, i)
s2 := palindrome(s, i, i+1)
if len(s1) > len(res) {
res = s1
}
if len(s2) > len(res) {
res = s2
}
}
return res
}
func palindrome(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)，其中 n 是字符串的长度。每个字符都可能作为中心进行扩展。
- 空间复杂度：O (1)，只使用了常数级别的额外空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
String s1 = palindrome(s, i, i);
String s2 = palindrome(s, i, i + 1);
if (s1.length() > res.length()) {
res = s1;
}
if (s2.length() > res.length()) {
res = s2;
}
}
return res;
}
public String palindrome(String s, int i, int j) {
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
return s.substring(i + 1, j);
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！