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 "";
    }
}