題目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

輸入與輸出

class Solution {
public:
    string longestPalindrome(string s) {
        
    }
};

樣例

1. Input："babad"，Output："bab"，Note："aba" is also a valid answer。
2. Input："cbbd"，Output："bb"。

題解與分析

解法一

鑒于 s 的最大長度為1000，可以考慮暴力解法，即枚舉每一個可能的中間位置，分別向兩側(cè)擴展，得到以該位置為中心的最長回文字串。枚舉過程中記錄最長回文子串的信息，最后返回子串即可。

該解法中需要注意的一點：回文子串的長度的奇偶性不確定，因此每個位置需要兩次擴展過程。

C++ 代碼如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size();
        int start = -1, length = 0; // 維護最長回文子串相關(guān)信息
        // 枚舉可能的中心位置
        for (int i = 0; i < size; ++i) {
            // 回文子串長度為奇數(shù)的情況
            int left = i - 1, right = i + 1;
            while (left >= 0 && right < size && s[left] == s[right])
                --left, ++right;
            if (right - left - 1 > length)
                start = left + 1, length = right - left - 1;
            // 回文子串長度為偶數(shù)的情況
            left = i, right = i + 1;
            while (left >= 0 && right < size && s[left] == s[right])
                --left, ++right;
            if (right - left - 1 > length)
                start = left + 1, length = right - left - 1;
        }
        return s.substr(start, length);
    }
};

該解法的時間復(fù)雜度為 O(n^2)。

解法二

與 3. Longest Substring Without Repeating Characters 類似，上述解法的時間復(fù)雜度高達 O(n^2) 的原因是沒有利用之前枚舉過程中得到的信息，導(dǎo)致大量重復(fù)的判斷。

下面介紹 Manacher 算法，該算法的時間復(fù)雜度為 O(n)，缺點是只能處理長度為奇數(shù)的回文子串（可以預(yù)處理字符串使該算法也適用于偶數(shù)長度子串）。

預(yù)處理過程：在原字符串兩端與字符之間插入原字符串中未出現(xiàn)過的字符（本文中使用 '#'），例如 abacabba 處理后為 #a#b#a#c#a#b#b#a#。這樣所有的回文子串均為奇數(shù)長度，例如 #a#b#a#、#a#b#b#a#。

設(shè)處理過的字符串為 Ma，建立一個同等長度的 int 數(shù)組 Mp。Mp[i]用來記錄以位置i為中心的最長回文子串的右半部分的長度（不包括位置i本身），例如#a#b#b#a#的右半部分為b#a#，相應(yīng)地，Mp[i] = 4。通過上例還可以得到Mp數(shù)組的另一個意義，它記錄了相應(yīng)回文子串在原字符串對應(yīng)的長度。

除此之外，建立變量Mx用來記錄當(dāng)前所有擴展過程中涉及到的最右側(cè)字符的位置，建立變量Id記錄擴展到該位置時的中心位置。

下面分情況討論該算法如何利用之前枚舉過程中的信息，也是該算法的核心，對應(yīng)代碼Mp[i] = Mx > i ? min(Mp[2 * Id - i], Mx - i) : 0;。

• 首先判斷Mx與i的位置關(guān)系：
• Mx > i：說明之前某個回文子串曾經(jīng)擴展到該位置右側(cè)，則該位置兩側(cè)字符中有一部分信息之前獲取過。這部分信息保存在Mp[2 * id - i]中，其中2 * id - i是i關(guān)于Id的對稱位置。進一步討論：
• Mp[2 * Id - i] <= Mx - i：即以2 * id - i為中心的最長回文子串在以id為中心的最長回文子串內(nèi)部，如下圖所示：
  
  
  由于橙色部分是回文子串，那么兩個紅色部分是鏡像關(guān)系，如果左側(cè)紅色部分是最長回文子串，那么右側(cè)紅色部分也是對應(yīng)位置的最長回文子串。即Mp[i] = Mp[2 * Id - i]。
• Mp[2 * Id - i] > Mx - i：即以2 * id - i為中心的最長回文子串的左側(cè)超出了以id為中心的最長回文子串。如下圖所示：
  
  
  與上種情況類似，但是以2 * id - i為中心的最長回文子串中只有紅色部分在以id為中心的最長回文子串內(nèi)部，因此右側(cè)對應(yīng)的紅色部分也是回文子串。但是在Mx右側(cè)的字符尚未拓展，因此需要進一步拓展獲得最大回文子串。初始化Mp[i] = Mx - i。
• Mx <= i：這種情況下i右側(cè)的字符尚未拓展過，需要拓展獲得最長回文子串。初始化Mp[i] = 0。

C++ 代碼如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size() * 2 + 1;
        char *Ma = new char[size];
        int *Mp = new int[size];
        int Mx = -1, Id = -1;
        int start, length = 0;
        Ma[0] = '#';
        for (int i = 0, p = 0; i < s.size(); ++i) {
            Ma[++p] = s[i];
            Ma[++p] = '#';
        }
        for (int i = 0; i < size; ++i) {
            Mp[i] = Mx > i ? min(Mp[2 * Id - i], Mx - i) : 0;
            while (i - Mp[i] - 1 >= 0 && i + Mp[i] + 1 < size && Ma[i - Mp[i] - 1] == Ma[i + Mp[i] + 1])
                ++Mp[i];
            if (i + Mp[i] > Mx)
                Mx = i + Mp[i], Id = i;
            if (Mp[i] > length)
                length = Mp[i], start = (i - Mp[i]) / 2;
        }
        delete[] Ma;
        delete[] Mp;
        return s.substr(start, length);
    }
};

時間復(fù)雜度分析：上述代碼中，第一個 for 循環(huán)為 O(n)，第二個 for 循環(huán)外層為 O(n)，下面分析內(nèi)部的 while 循環(huán)。由上述算法流程可知，每一次擴展操作都是在Mx右側(cè)擴展，即每執(zhí)行一次++Mp[i];都會導(dǎo)致Mx增加 1，即Mx單調(diào)遞增。因為Mx的取值范圍是[0, size)，所以 while 循環(huán)內(nèi)部代碼最多執(zhí)行 O(n) 次。

該解法的時間復(fù)雜度為 O(n)。