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"

窮舉法

這個(gè)字符串的最大長(zhǎng)度為1000，那么窮舉法也不會(huì)有太大的計(jì)算量

解題思路

窮舉法的思路比較簡(jiǎn)答，就是遍歷每個(gè)字符以其為中心的回文串，記錄最大值

代碼實(shí)現(xiàn)

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