LC 5、最长回文子串

superJade / 2023-07-30 / 原文

LC 5、最长回文子串

题目描述

这是LeetCode 上的 5、最长回文子串，难度为中等

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

示例：

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

1 <= s.length <= 1000
s仅由数组和英文字母（大写和/或小写）组成

本题有时间限制，我们如果使用枚举子串的方法必然超时，所以我们如果要枚举暴力，也应该做出更优美的暴力算法

朴素解法

枚举字符串 s中的每一位，作为回文串的中心点，左右进行扩展，直到达到边界或者不满足回文串定义为止。

当我们有一个简单的实现方法之后，需要从题目的数据规模，计算机的处理速度和实现方法的计算量出发，判断这样的作法是否会超时。

由于字符串长度最多只有1000，而我们的实现方法是O(n^2)，因此我们算法计算量在10e6，是在计算机每秒的处理范围内的。

首先枚举回文串的中心i，然后分情况向两边扩展边界，直到达到边界或者不满足回文子串定义为止：

回文串长度为奇数，判断s[i - k] == s[i + k]，k = 1, 2, 3, ...
回文串长度为偶数，判断s[i - k] == s[i + k - 1], k = 1. 2, 3, ...

代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0 , end = 0;
        for(int i = 0 ; i < s.size(); i++){
            auto [l1, r1] = getstr(s, i, i);
            auto [l2, r2] = getstr(s, i, i + 1);
            if(end - start < r1 - l1){
                end = r1;
                start = l1;
            }
            if(end - start < r2 - l2){
                end = r2;
                start = l2;
  s          }
        }
        return s.substr(start, end - start + 1);
    }

    pair<int, int> getstr(string& s, int l , int r){
        while(l >= 0 && r < s.size() && s[l] == s[r]){
            l--;
            r++;
        }
        return {l + 1, r - 1};
    }
};

时间复杂度：先枚举了 s中的每个字符作为回文串的中心点，再从中心点左右扩展，最多扩展到边界。复杂度为 O(n^2)
空间复杂度：O(1)

Manacher 算法(扩展)--三叶姐yyds(摘录自宫水三叶的刷题日记)

这是一个比较冷门的算法，使用范围也比较单一，只能用于解决【回文串】问题。Manacher是【回文串】问题的最优解。

Manacher算法较长，为了避免回文串长度奇偶问题的分情况讨论，在这里会原字符进行了处理，在边界和字符之间插入占位符。

使用了这样的技巧之后，当非占位字符作为回文串的中心时，对应了回文串长度为奇数的情况；当占位字符作为回文串的中心时，对应了回文串长度为偶数的情况。

class Solution {
public:
    int expand(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return (right - left - 2) / 2;
    }

    string longestPalindrome(string s) {
        int start = 0, end = -1;
        string t = "#";
        for (char c: s) {
            t += c;
            t += '#';
        }
        t += '#';
        s = t;

        vector<int> arm_len;
        int right = -1, j = -1;
        for (int i = 0; i < s.size(); ++i) {
            int cur_arm_len;
            if (right >= i) {
                int i_sym = j * 2 - i;
                int min_arm_len = min(arm_len[i_sym], right - i);
                cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
            } else {
                cur_arm_len = expand(s, i, i);
            }
            arm_len.push_back(cur_arm_len);
            if (i + cur_arm_len > right) {
                j = i;
                right = i + cur_arm_len;
            }
            if (cur_arm_len * 2 + 1 > end - start) {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }
        }

        string ans;
        for (int i = start; i <= end; ++i) {
            if (s[i] != '#') {
                ans += s[i];
            }
        }
        return ans;
    }
};

Label：模拟，回文串