LeetCode 5. 最长回文子串

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

解题思路

比较选中的元素两侧，判断是否是回文。需要注意的是要考虑偶数和奇数长度

解答

执行用时4ms。

char* longestPalindrome(char* s)
{
    int start = 0, maxlen = 0, i = 0;
    int len = strlen(s);
    
    if (len <= 1)
        return s;

    /* 注意i的最大值限制，在此位置之后的情况不需要考虑 */
    for (int i = 1; i < len - (maxlen / 2); i++)
    {
        /* 以0.5,1.5,2.5等为中心比较两侧，看是否是回文 */
        int low = i - 1;
        int high = i;
        while (low >= 0 && high < len && s[low] == s[high])
        {
            low--;
            high++;
        }
        /* 上面的判断条件跳出时high比真实的+1，low比真实的-1 */
        if (high - low - 1 > maxlen)
        {
            maxlen = high - low - 1;
            start = low + 1;
        }
        
        /* 以1,2,3等为中心比较两侧，看是否是回文 */
        low = i - 1; high = i + 1;
        while (low >= 0 && high < len && s[low] == s[high])
        {
            low--;
            high++;
        }
        if (high - low - 1 > maxlen)
        {
            maxlen = high - low - 1;
            start = low + 1;
        }
    }
    
    /* maxlen表示回文子串的长度，start表示该回文子串在s中的起始下标 */
    char *arr = (char *)malloc(sizeof(int) * maxlen + 1);
    
    for (i = 0; i < maxlen; i++, start++)
        arr[i] = s[start];
    
    arr[i] = '\0';

    return arr;
}