[LeetCode]Longest Palindromic Substring

题目：Longest Palindromic Substring

查找最长回文子串

思路：

一个指针从头部，一个指针从尾部，对比每一个字母，若相等则可能是回文子串，则，检测子串是否回文，是则比较和已知的子串长度，更长就记录其起始和终止坐标，否则就放弃。

/**********************************************************************
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
**********************************************************************/
#include <stdio.h>
#include <ctype.h>

char* longestPalindrome(char* s) {
    int length = strlen(s);
    int i,j,max = 1,maxi = 0,maxj = 0,flag = 1;//flag标志是否是回文子串
    for(i = 0;i < length && i + max < length;i++){//从头开始检测，最后剩余未检测长度少于一直最长解则放弃
        for(j = length - 1;j > i;j--){//从尾部开始检测
            flag = 1;
            if(s[i] == s[j]){//可能回文
                int head = i + 1,tail = j - 1;
                while(head < tail){//检测是否是回文子串
                    if(s[head] != s[tail]){
                        flag = 0;
                        break;
                    }
                    head++;
                    tail--;
                }
                if(flag == 1){//如果是回文子串
                    if(max < j - i + 1){//长度是否比已知最优解长
                        max = j - i + 1;
                        maxi = i;
                        maxj = j;
                    }
                    break;//继续收缩尾部指针，也得不到更优的解，所以放弃
                }
            }
        }
    }

    char *substr = (char *)malloc((max + 1)*sizeof(char));
    memset(substr,0,(max + 1)*sizeof(char));
    strncpy(substr,s + maxi,max);
    return substr;
}

void main(){
    char s[] = "babadada";
    char *sp = longestPalindrome(s);
    printf("%s
",sp);
    free(sp);
}

上面的思路是从两边向中间收束，另一个思路是从中间向两边发散。

具体如下：

先找当前下标为中心的回文子串，比较它和最优解，更优则更新最优解，

递归查找中心点向左和向右偏移后的回文子串。

/**********************************************************************
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
**********************************************************************/
#include <stdio.h>
#include <ctype.h>

int max = 1;//记录已知最长的回文子串的长度
int maxi = 0;//记录已知最长的回文子串的头部坐标
int maxj = 0;//记录已知最长的回文子串的尾部坐标

void longestPSubstring(char *s,int i){//记录当前搜索的位置
    int head = i - 1;
    int tail = i + 1;
    int length = strlen(s);
    while((head >= 0 || tail < length) && s[head] == s[tail]){//检测以i为中心的回文子串
        head--;
        tail++;
    }
    if(tail - head - 1 > max){//比较以i为中心的回文子串是否更长
        maxi = head + 1;
        maxj = tail - 1;
        max = tail - head - 1;
    }
    
    if(i - 1 > 0){
        longestPSubstring(s,i - 1);//向左偏移
    }
    if(i + 1 < length - 1){
        longestPSubstring(s,i + 1);//向右偏移
    }
}

char* longestPalindrome(char* s) {
        int length = strlen(s);
    longestPSubstring(s,length/2);

    char *substr = (char *)malloc((max + 1)*sizeof(char));
    memset(substr,0,(max + 1)*sizeof(char));
    strncpy(substr,s + maxi,max);
    return substr;
}

void main(){
    char s[] = "babadada";
    char *sp = longestPalindrome(s);
    printf("%s
",sp);
    free(sp);
}