Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
穷举法
这个字符串的最大长度为1000，那么穷举法也不会有太大的计算量
解题思路
穷举法的思路比较简答，就是遍历每个字符以其为中心的回文串，记录最大值
代码实现
char* longestPalindrome(char* s) {
int i, j, l, r, max, n;
int rl, rr;
n = strlen(s);
max = 0;
for (i = 0; i < n; i++) {
l = r = i;
while (l > 0 && s[l-1] == s[i]) l--;
while (r < n - 1 && s[r+1] == s[i]) r++;
while (l > 0 && r < n - 1 && s[l-1] == s[r+1]) {
l --;
r ++;
}
if (r - l + 1 > max) {
max = r - l + 1;
rl = l;
rr = r;
}
}
if (max > 0) {
char* p = malloc((max + 1)*sizeof(char));
p[max] = '\0';
memcpy(p, s+rl, max);
return p;
} else {
return "";
}
}
