LeetCode-5.最长回文子串-C

1.最长回文子串

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

示例 1：
1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
1
2
输入：s = "cbbd"
输出："bb"
提示：

1 <= s.length <= 1000

s 仅由数字和英文字母组成
1
2
3
char* longestPalindrome(char* s) {
    
}

2.个人思路

我的思路是，从第二位字符串开始往前和往后遍历，这里要注意第二个for循环的大小。因为是两边同时遍历，所以要考虑谁先遍历完成了，也就是for循环要遍历小的一端，一端结束后，就可以停止遍历了。

还需要注意的是，示例2给出的cbbd，因为是两端遍历，这里明显不符合以上想法，但是这是个特殊的例子，如果是cbbbd，就符合了。所以拿出来和上面并列else if判断一下，如果当前开始遍历的中值等于左边或者右边的值，就加1。但是很快发现问题，在第一个例子中，babad的中位值b，和开头的b是一样的，但是开头的b和d不一样，跳转到else if里面，发现b = b，加一了，显然是错误的，因此在此基础上，又加入了标志位的判断，中位的前一个或者后一个相同的话，才会出现连续的，偶数的字符串，所以加上标志位后，就正常了。

但是经过调试发现，输入c1bbbbc又出现问题了，因为中位为第二个b时候，c = c 又加了两个。这里简单修改就行了。

但是提交后发现，没有考虑到最长回文子串为1的时候。。。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
char* longestPalindrome(char* s) {
  int size = 1,max = 0,index = 0,stat_index= 0;  /*记录最长的回文子串*/
    char *first,*next;
    char *string = s;
    char *temp = NULL;
    int flag = 0,stats = 0;
    int num = strlen(s);

    for (int i = 1; i < num-1; ++i) {  /*从第二个字符开始遍历*/
        s++;
        first = s - 1;
        next =  s + 1;
        if(*first == *s || *next == *s) /*出现下面else if情况*/
            flag = 1;
            
        for (int j = 1; j <= ((i < num-1-i) ? i : num-1-i); ++j) {
            first = s - j;
            next = s + j;
            if((*first == *next) && (stats == 0))  /*赋值 奇数类型*/
            {
                size+=2;
            }
            else if( (*s == *first || *s == *next ) && flag == 1)   /*重复的 偶数类型*/
            {
                if(*s == *next)  /*右边*/
                {
                    stat_index++;
                }
                stats = 1;
                size+=1;
            }
            if(max < size) {
                max = size;
                index = i - j;
            }
        }
        index += stat_index;
        stat_index = 0;
        flag = 0;
        size = 1;   /*重新计算*/
        stats = 0;
    }
    temp = (char *)malloc((max+1) * sizeof(char));
    strncpy(temp, string + index, max);
    temp[max] = '\0';
    return temp;  
}
放弃了，不想写了。一开始思路就是错的，越改错越多。

3.官方解析

我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。

char * longestPalindrome(char * s){
    int N = strlen(s), start = 0, len = 0;  // N 字符串长度， start 子串起始位置， len 子串长度
    for (int i = 0; i < N; i++) {   // 奇数长度的回文子串
        int left = i - 1, right = i + 1;
        while (left >= 0 && right < N && s[left] == s[right]){
            left--; right++;            // 以 i 为中心，向两侧延伸，直到不再满足回文
        }                               // left+1 ~ right-1 则为以i为中心的最大回文子串
        if (right - left - 1 > len) {   // 若更长，则保存该子串信息
            start = left + 1;
            len = right - left - 1;
        }
    }
    for (int i = 0; i < N; i++) {   // 偶数长度的回文子串
        int left = i, right = i + 1;    // 以 i+0.5 为中心，向两侧延伸
        while (left >=0 && right < N && s[left] == s[right]) {
            left--, right++;
        }
        if (right - left - 1 > len) {
            start = left + 1;
            len = right - left - 1;
        }
    }
    s[start + len] = '\0';      // 原地修改返回
    return s + start;
}

这位大佬的代码