最长回文子串
题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000
摘要
回文是一个正读和反读都相同的字符串，例如{“aba”}“aba” 是回文，而{“abc”}“abc” 不是。
解决方案
观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n - 1个这样的中心。
为什么会是 2n - 1个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如{“abba”}“abba” 的中心在两个{‘b’}‘b’ 之间）
代码实现
int expandAroundCenter(char *s, int left, int right) {
int L = left;
int R = right;
while (L >= 0 && R < strlen(s) && s[L] == s[R]) {
L--;
R++;
}
return R - L - 1;
}
char* longestPalindrome(char* s) {
if (s == NULL) {
return NULL;
}
int start = 0;
int end = 0;
size_t size = strlen(s);
for (int i = 0; i < size; i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = len1 > len2 ? len1 : len2;
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
int len = end - start + 1;
char *dst = (char *)malloc(sizeof(char) * len);
strncpy(dst, s + start, len);
free(dst);
return dst;
}
复杂度分析
- 时间复杂度：O(n^2)， 由于围绕中心来扩展回文会耗去 O(n) 的时间，所以总的复杂度为 O(n^2)
- 空间复杂度：O(1)
