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

示例 1：

输入：s = "babad"

输出："bab"

解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"

输出："bb"

示例 3：

输入：s = "a"

输出："a"

示例 4：

输入：s = "ac"

输出："a"

暴力解法是枚举出所有子串，看哪个子串长度最长。时间复杂度可以达到O(n^3)，这种级别的复杂度，长度达到1000几乎是不可取的。

我们看一下其中一种解法叫中间扩展法。所谓中间扩展法，就是从一个中心往两边扩展。非常符合回文串的定义。比如，level，从中间v向左右分别扩展可以得出，e相等，l相等，则level为回文串。长度为5，没有比它更长的回文子串，则它就是答案。leveloppo字符串中，回文子串level的长度为5，oppo的长度为4，则最长回文子串是level。

int expanLen(char * s, int L, int R){    int left = L, right = R;    while (left >= 0 && right < strlen(s) && s[left] == s[right])    {//大于左边界，小于右边界，对称相等。接着找下一对儿        left--;        right++;    }//返回找到子串的长度    return  right - left - 1;}

如果s[left] == s[right]，则继续向两边扩展；当不相等时，返回该回文子串的长度为right - left - 1。

核心思想：

中间扩展法，需要有一个中间点。像回文子串level的中间点为字母v，可以以v为中心向两边扩展；像回文子串oppo的中间点则为pp，可需要以pp为中心向两边扩展。

 int SubLen1 = expanLen(s, i, i + 1);//长度为偶数时，从中间向两边扩展 int SubLen2 = expanLen(s, i - 1, i + 1);//长度为奇数时，从中间向两边扩展

当我们对奇数串level进行扩展时，把 i - 1 赋值给left，把 i + 1 赋值给right；当我们对偶数串oppo进行扩展时，把 i 赋值给left，把 i + 1 赋值给right。这样就实现了以不同中心向两边扩展的思想，实现了奇偶回文串的统一。

int SubLen = SubLen1 > SubLen2 ? SubLen1 : SubLen2;//选奇数偶数子if (SubLen > longPalinEnd - longPalinStart + 1){//当前子串比上次子串长，则更新最长子串的初始位置和结束位置      longPalinStart = i - (SubLen - 1) / 2;      longPalinEnd = i + SubLen / 2;  }   

扩展遍历完不同子串之后，判断哪个子串的长度更长。选出更长的子串，同时更新长回文子串的其起点和终点，便于输出最长回文子串。

完整代码如下：

#include<stdio.h>#include<stdlib.h>#include<string.h> int expanLen(char * s, int L, int R){    int left = L, right = R;    while (left >= 0 && right < strlen(s) && s[left] == s[right])    {//大于左边界，小于右边界，对称相等。接着找下一对儿        left--;        right++;    }//返回找到子串的长度    return  right - left - 1;}char * longestPalindrome(char * s){    if (s == NULL || strlen(s) < 1)return s;       int longPalinStart = 0, longPalinEnd = 0;//最长初始位置和结束位置    for (int i = 0; i < strlen(s); i++)    {        int SubLen1 = expanLen(s, i, i + 1);//长度为偶数时，从中间向两边扩展        int SubLen2 = expanLen(s, i - 1, i + 1);//长度为奇数时，从中间向两边扩展        int SubLen = SubLen1 > SubLen2 ? SubLen1 : SubLen2;//选奇数偶数子串        if (SubLen > longPalinEnd - longPalinStart + 1)        {//当前子串比上次子串长，则更新最长子串的初始位置和结束位置            longPalinStart = i - (SubLen - 1) / 2;            longPalinEnd = i + SubLen / 2;        }       }    s[longPalinEnd + 1] = '\0';//子串后边加结束符    return s + longPalinStart;}int main(){    char s[] ="ovvolel";    char* s1 = longestPalindrome(s);    printf("%s\n", s1);        return 0;}

接下来的两篇文章为，LeetCode5.1-马拉车算法求解最长回文子串 和

LeetCode5.2-动态规划求解最长回文子串

leetcode2. 两数相加-c语言-python3

LeetCode4. 寻找两个正序数组的中位数