最长回文子串

题目：

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

思路：

1.逐个遍历，中心扩散法：

首先我们看到这个题，一个回文子串其实分为两种，一种是奇数型回文子串，一种是偶数型回文子串，奇数型回文子串有一个字符作为对称中心，其两侧字符一一对应回文，而偶数回文子串则没有字符作为对称中心。所以我们在做这个题目的时候其实要分为两种情况来分析。

第一种奇数型回文子串，以i为对称中心，向i的两侧分散来判断i-1和i+1对应的位置字符是否相同，分析时注意考虑字符数组边界问题，不要出现字串数组越界的问题。

第二种偶数型回文数组，以i和i+1中间为对称中心。先判断i和i+1是否对称。

最后注意的几点就是首先要在遍历的同时记录最长回文子串的长度，同时记录最长回文子串的起点位置，这样有利于最后得到最长回文子串。在C语言中我们得到一条字符串的方式为查看起点位置，直到‘/0’为止，所以我们需要字符串长度和最长字符串起点位置。

代码实现：

//重复的判断两个为止字符是否相等，可以用函数进行表示
void help(char* s, int N, int left, int right, int* start, int* len){
    while(left>=0&&right<N&&s[left]==s[right]){
        left--;right++;
    }
    if(right-left-1>*len){
        *start=left+1;
        *len=right-left-1;
    }
}
char * longestPalindrome(char * s){
    int N=strlen(s), start=0, len=0;
//最长回文子串为奇数情况
    for(int i=0;i<N;i++){
        help(s, N, i-1, i+1, &start, &len);
    }
//最长回文字串为偶数情况
    for(int i=0;i<N;i++){
         help(s, N, i, i+1, &start, &len);
    }
//截取最长回文子串
    s[start+len]='\0';
    return s+start;
}

2.动态规划

首先我们需要复习一下动态规划的四大基本特点：

1.动态规划的题一般涉及的都是求解最优解的问题（此题即求出最长回文字串

2.整体问题的最优解是依赖各个小问题的最优解（所以我们在求解整体问题的最优解的前提一定是已经求出了局部问题的最优解

3.大问题可以分解成若干个小问题，其中小问题还有许多相互重叠的更小子问题

4.为了避免重复，我们在进行动态规划的时候可以从下往上进行分析（在这个题中即是不断枚举回文子串，从len=2的子串进行查验，len>3的都依赖更小子问题的回文情况，比如len=4的回文子串，最外侧两个字符相等，其实要查验内部len=2是否为回文子串。

代码实现：

char * longestPalindrome(char * s){
    int n=strlen(s);
    if(n<2){
        return s;
    }
    int maxlen=1, start=0;
    int dp[n][n];
    for(int i=0;i<n;i++){
        dp[i][i]=true;
    }
    for(int L=2;L<=n;L++){
        for(int i=0;i<n;i++){
            int j=i+L-1;
            if(j>=n){
                break;
            }
            if(s[i]!=s[j]){
                dp[i][j]=false;
            }else{
                if(j-i<3){
                    dp[i][j]=true;
                }else{
                    dp[i][j]=dp[i+1][j-1];
                }
            }
            if(dp[i][j]&&j-i+1>maxlen){
                maxlen=j-i+1;
                start=i;
            }
        }
    }
    s[start+maxlen]='\0';
    return s+start;
}