最长回文子串（Leetcode-5）-中心扩散法（回文串）

题目

• 原题连接：https://leetcode-cn.com/problems/longest-palindromic-substring/

  

知识点

• 中心扩散法（针对回文串）

思路

• 对于一个子串而言，如果它是回文串，并且长度大于 2，那么将首尾的两个字母去掉以后，它仍然是个回文串。例如对于字符串

  “acbca”

  ，去掉首位的

  “a”

  以后，

  “cbc”

  仍然是回文串。
• 我们可以从上述的例子中看出，我们选取某个元素

  i

  ，从中心分别往两侧去扩散，直到两侧不一致为止，那么我们就可以获得以

  i

  元素为中心的最大回文串。那么从第一个元素遍历至最后一个元素，那么我们就可以找到最大的字串。
• 但是，在如下的例子中会出现问题

  “abba”

  ，由于在上面思路中，我们的中心选取的是一个元素，这导致我们无法去找到以

  “bb”

  这种，以两个元素作为中心的回文串。因此，我们在Line 23中，设置判断语句

  s[i] == s[i + 1]

  ，判断时候后一个也是相同的元素。如果相同，那么可能存在如

  “abba”

  的可能（

  i=1

  时，

  s[i] == s[i + 1]

  ），那我们就把

  s[i]

  和

  s[i+1]

  连起来作为中心，再向两侧去扩散，找到其最大回文串。

代码

• 速度比我想象的快

  

class Solution {
public:
    int max_len = 0, max_left, max_right;

    string longestPalindrome(string s) {
        if (s.length() == 1) return s;  // 特例
        if (s.length() == 2 && s[0] == s[1]) return s;  // 特例

        for (int i = 0; i <= s.length() - 2; i++) {  // 中心扩散
            // 长度为1的情况
            int len = 1, left = i, right = i;  // 向外扩散的距离
            while (i - len >= 0 && i + len < s.size()) {
                if (s[i - len] != s[i + len]) break;  // 扩散结束
                left = i - len, right = i + len;
                len++;
            }
            if ((right - left) > max_len) {  // 大于当前最长字串长度
                max_len = right - left;
                max_left = left, max_right = right;
            }

            // 中心为2的情况(仅[i]与[i+1]相等)
            if (s[i] == s[i + 1]) {
                if (max_len < 1) max_len = 1, max_left = i, max_right = i + 1;
                len = 1;
                while (i - len >= 0 && (i + 1) + len < s.size()) {
                    if (s[i - len] != s[i + 1 + len]) break;  // 扩散结束
                    left = i - len, right = (i + 1) + len;
                    len++;
                }
                if ((right - left) > max_len) {  // 大于当前最长字串长度
                    max_len = right - left;
                    max_left = left, max_right = right;
                }
            }

        }
        return s.substr(max_left, max_len + 1);
    }
};