LeetCode 5.最长回文子串

题目

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

示例

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

题目链接

题目分析

暴力

题目要求我们求最长回文子串，所以我们把所有长度大于等于2的子串都遍历一遍就好，但是这种方式在很多语言中会超时，时间复杂度太高，显然需要找到时间复杂度更低的方法。
完整过程见最后。

中心扩散法

中心扩散其实就是以一个点（或两个点，中心扩散需要区分起点奇偶性）开始向外扩散，直到字符串不是回文为之，中心扩散法的基本过程如下：

int len = s.length();
while (l >= 0 && r < len) {
    if (s[i] != s[l]) break;
    l--;
    r++;
}
return {l + 1, r - 1}

需要注意区分起点奇偶性，时间复杂度是O(N^2)，完整过程见最后。

题目解答

暴力

bool isPal(char* s, int l, int r){
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++;
        r--;
    }
    return true;
}

char * longestPalindrome(char * s){
    int len = strlen(s);
    if (len == 0 || len == 1) return s;
    // 先写一个暴力
    int count = 0;
    int max = 0;
    int start = 0;
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if(j - i + 1 > max && isPal(s, i, j)){
                start = i;
                max = j - i + 1;
            }
        }
    }
    if (max == 0) {
        char* res = (char*)calloc(2, sizeof(int));
        res[0] = s[0];
        return res;
    }
    char* res = (char*)calloc(max + 1, sizeof(char));
    for (int i = 0, j = start; i < max; i++, j++) {
        res[i] = s[j];
    }
    return res;
}

中心扩散法

class Solution {
public:
    // 中心扩散
    pair<int, int> centerSpread(string s, int l, int r) {
        int len = s.length();
        while (l >= 0 && r < len) {
            if (s[l] != s[r]) break;
            l--;
            r++;
        }
        return {l + 1, r - 1};
    }

    string longestPalindrome(string s) {
        int len = s.length();
        if (len == 0 || len == 1) return s;
        int start = 0;
        int end = 0;
        for (int i = 0; i < len - 1; i++) {
            auto [left1, right1] = centerSpread(s, i, i); 
            auto [left2, right2] = centerSpread(s, i, i+1);
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};