Sun's Blog
0%

leetcode 5. 最长回文子串

发表于 更新于 分类于

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

示例 3：

1
2
输入：s = "a"
输出："a"

示例 4：

1
2
输入：s = "ac"
输出："a"

思路：

​ 从头开始遍历字符串，设left , right两个指针分别指向当前字符的左右，如left所指字符与当前字符相等，则指针需往前移动(left>=0)，right指针同理向后移动(right<s.length())，left与right都无法移动后，再判断left与right所指的字符是否相同，每个字符的中心扩散对应一个maxsize，遍历结束后返回maxsize的一段字符的起始位置与size.

代码:

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
30
31
32
33
34
35
36
37
38
string longestPalindrome(string s) {
	if (s.length() == 0) {
		return "";
	}
	int slen = s.length();
	int left = 0;
	int right = 0;
	int len = 1;
	int maxStart = 0;
	int maxLen = 0;

	for (int i = 0; i < slen; i++) {
		left = i - 1;
		right = i + 1;
		while (left >= 0 && s[left] == s[i]) {
			len++;
			left--;
		}
		while (right < slen && s[right] == s[i]) {
			len++;
			right++;
		}
		while (left >= 0 && right < slen && s[right] == s[left]) {
			len = len + 2;
			left--;
			right++;
		}
		if (len > maxLen) {
			maxLen = len;
			maxStart = left;
		}
		len = 1;
	}
	return s.substr(maxStart+1, maxLen);

}