LeetCode 題解 | 5. 最長迴文子串

07-16

來自專欄領扣（LeetCode）9 人贊了文章

題目描述：

給定一個字元串 s，找到 s 中最長的迴文子串。你可以假設 s 的最大長度為1000。

示例 1：

輸入: "babad"輸出: "bab"注意: "aba" 也是一個有效答案。

示例 2：

輸入: "cbbd"輸出: "bb"

最長迴文子串 - LeetCode (中國)?

leetcode-cn.com

摘要：

這篇文章是為中級讀者而寫的。它介紹了迴文，動態規劃以及字元串處理。請確保你理解什麼是迴文。迴文是一個正讀和反讀都相同的字元串，例如， $「aba」$ 是迴文，而 $「abc」$ 不是。

方法一、最長公共子串：

常見錯誤

有些人會忍不住提出一個快速的解決方案，不幸的是，這個解決方案有缺陷（但是可以很容易地糾正）：

反轉 $S$ ，使之變成 $S′?$ 。找到 $S$ 和 $S′?$ 之間最長的公共子串，這也必然是最長的迴文子串。

這似乎是可行的，讓我們看看下面的一些例子。

例如， $S=「caba」$ ， $S′?? =「abac」$ ：

$S$ 以及 $S′?$ 之間的最長公共子串為 $「aba」$ ，恰恰是答案。

讓我們嘗試一下這個例子： $S=「abacdfgdcaba」$ ， $S′??=「abacdgfdcaba」$ ：

$S$ 以及 $S′?$ 之間的最長公共子串為 $「abacd」$ ，顯然，這不是迴文。

演算法

我們可以看到，當 $S$ 的其他部分中存在非迴文子串的反向副本時，最長公共子串法就會失敗。為了糾正這一點，每當我們找到最長的公共子串的候選項時，都需要檢查子串的索引是否與反向子串的原始索引相同。如果相同，那麼我們嘗試更新目前為止找到的最長迴文子串；如果不是，我們就跳過這個候選項並繼續尋找下一個候選。

這給我們提供了一個複雜度為 $O(n^2)$ 動態規劃解法，它將佔用 $O(n^2)$ 的空間（可以改進為使用 $O(n)$ 的空間）。請在這裡閱讀更多關於最長公共子串的內容。

方法二、暴力法：

很明顯，暴力法將選出所有子字元串可能的開始和結束位置，並檢驗它是不是迴文。

複雜度分析

時間複雜度： $O(n^3)$ ，假設 $n$ 是輸入字元串的長度，則 $left( _{2}^{n} ight)=frac{n(n-1)}{2}$ 為此類子字元串(不包括字元本身是迴文的一般解法)的總數。因為驗證每個子字元串需要 $O(n)$ 的時間，所以運行時間複雜度是 $O(n^3)$ 。
空間複雜度： $O(1)$ 。

方法三、動態規劃：

為了改進暴力法，我們首先觀察如何避免在驗證迴文時進行不必要的重複計算。考慮 $「ababa」$ 這個示例。如果我們已經知道 $「bab」$ 是迴文，那麼很明顯， $「ababa」$ 一定是迴文，因為它的左首字母和右尾字母是相同的。

我們給出 $P(i,j)$ 的定義如下：

$P(i,j)=true$ ，如果子串 $S_{i}...S_{j}$ 是迴文子串
$P(i,j)=false$ ，其他情況

因此， $P(i,j)=(P(i+1,j?1) and S_{i}==S_{j})$

基本示例如下：

$P(i,i)=true$
$Pleft( i,i+1 ight)=left( S?_{i}? ==S?_{i+1} ight)$

這產生了一個直觀的動態規劃解法，我們首先初始化一字母和二字母的迴文，然後找到所有三字母迴文，並依此類推…

複雜度分析

時間複雜度： $O(n^2)$ ，這裡給出我們的運行時間複雜度為 $O(n^2)$ 。
空間複雜度： $O(n^2)$ ，該方法使用 $O(n^2)$ 的空間來存儲表。

補充練習

你能進一步優化上述解法的空間複雜度嗎？

方法四、中心擴展演算法：

事實上，只需使用恆定的空間，我們就可以在 $O(n^2)$ 的時間內解決這個問題。

我們觀察到迴文中心的兩側互為鏡像。因此，迴文可以從它的中心展開，並且只有 $2n?1$ 個這樣的中心。

你可能會問，為什麼會是 $2n?1$ 個，而不是 $n$ 個中心？原因在於所含字母數為偶數的迴文的中心可以處於兩字母之間（例如 $「abba」$ 的中心在兩個 $『b』$ 之間）。

public String longestPalindrome(String s) { int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1);}private int expandAroundCenter(String s, int left, int right) { int L = left, R = right; while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { L--; R++; } return R - L - 1;}

複雜度分析

時間複雜度： $O(n^2)$ ，由於圍繞中心來擴展迴文會耗去 $O(n)$ 的時間，所以總的複雜度為 $O(n^2)$ 。
空間複雜度： $O(n)$ 。

方法五、Manacher 演算法：

還有一個複雜度為 $O(n)$ 的 Manacher 演算法，你可以在這裡找到詳盡的解釋。然而，這是一個非同尋常的演算法，在45分鐘的編碼時間內提出這個演算法將會是一個不折不扣的挑戰。但是，請繼續閱讀並理解它，我保證這將是非常有趣的。