最長回文子串（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);
    }
};