LeetCode No5. 最长回文子串 题解

一、题目

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

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

示例 3：
输入：s = “a”
输出：“a”

示例 4：
输入：s = “ac”
输出：“a”

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

二、解题思想

寻找回文串，核心就是串的对称。仅从一头找的话很难确定另一头的终点位置。利用回文串的对称性，我们可以

1. 从两端出发向内寻找
2. 也可以选定一个中心点向两端扩散。

按照第一种方式（双指针），实现起来我们会发现，两端的位置也难以确定。例如，我们选定主串的头和尾当初始子串，如果该子串不满足回文，那么下一个子串该如何寻找呢？

是左边向右移动一位？

还是右边向左移动一位？

还是左右都移动一位？

再往后列举的话，相当于穷举了，因此看来这貌似并不是一个很好的解决办法。（至少粗略来看，目前没有什么思路）

因此，我们可以选择第二种方式，以每一个字符为中心，向两端扩张寻找最大回文子串，就像这样：

当然，你会发现，我们漏了一个回文串 “adccda”，因为这个回文串长度为奇数，因此我们还需要像这样寻找：

最后比较两种情况寻找的最长回文子串哪个更长就可以啦！

三、代码

class Solution {
public:
    // 寻找奇数长度的回文子串
    // s：主串
    // index：中心出发点
    // left：最长回文子串起始位置
    // right：最长回文子串终点位置
    // len：最长回文子串的长度
    void oddPlalindrome(const string &s, int index, int &left, int &right, int &len) {
        int t_len = 1, t_left = index, t_right = index;    // 临时长度、子串左右位置
        while (t_left >= 1 && t_right < s.size() - 1)      // 保证子串不出界
        {
            if (s[t_left - 1] != s[t_right + 1]) break;    // 向两端延展，如果不同则直接退出循环
            // 更新临时长度和子串位置
            t_len += 2;                                   
            --t_left; ++t_right;
        }
        // 如果这次长度更长，更新子串位置和长度
        if (t_len >= len)
        {
            len = t_len;
            left = t_left;
            right = t_right;
        }
    }

    // 寻找偶数长度的回文子串
    void evenPlalindrome(const string &s, int index, int &left, int &right, int &len) {
        int t_len = 2, t_left = index, t_right = index + 1;    // 初始长度 t_len 设为 2
        if (s[t_left] != s[t_right]) return;                   // 如果相邻的两个字符不一样，直接退出函数
        // 同上
        while (t_left >= 1 && t_right < s.size() - 1)
        {
            if (s[t_left - 1] != s[t_right + 1]) break;
            t_len += 2;
            --t_left; ++t_right;
        }
        if (t_len >= len)
        {
            len = t_len;
            left = t_left;
            right = t_right;
        }
    }

    string longestPalindrome(string s) {
        int left, right, len = 0;
        // 以每个字符为中心，扩散寻找最大子串
        for (int i = 0; i < s.size(); ++i)
        {
            oddPlalindrome(s, i, left, right, len);
            evenPlalindrome(s, i, left, right, len);
        }
        return string(s.begin() + left, s.begin() + right + 1);
    }
};

四、复杂度分析

时间复杂度：

一般情况下，时间复杂度为 O(n)，因为 oddPlalindrome 和 evenPlalindrome 两个函数的耗时趋近于常数。

最坏情况下，时间复杂度为 O(n²)，此时串中具有较长的连续相同字符或间歇周期性字符，例如 “aaaaaaaaaa”，“ababababababa”，可以在源代码基础上添加判断情况进行优化。

空间复杂度：

oddPlalindrome 和 evenPlalindrome 函数没有开辟新的大内存空间，因此复杂度为 O(1)。

五、算法评价

LeetCode 中：

执行用时：16 ms, 在所有 C++ 提交中击败了92.31%的用户

内存消耗：6.9 MB, 在所有 C++ 提交中击败了95.50%的用户

提交了很多次，整体时间稳定在 16 ~ 20ms，内存消耗稳定在 6.9 ~ 7.0ms。