leetcode地址：5. 最長回文子串

解答參考：動態規劃、中心擴散、Manacher 算法

問題描述：

給你一個字符串?s，找到?s?中最長的回文子串。比如給定字符串s = "babad" ，找出最長的回文子串為"bab"

算法思路：

本題可以采用暴力破解法、中心擴散法、Manacher算法3種方法，本篇文章講解暴力破解法。

暴力法采用雙指針兩邊夾，驗證是否是回文子串。除了枚舉字符串的左右邊界以外，比較容易想到的是枚舉可能出現的回文子串的“中心位置”，從“中心位置”嘗試盡可能擴散出去，得到一個回文串。因此中心擴散法的思路是：遍歷每一個索引，以這個索引為中心，利用“回文串”中心對稱的特點，往兩邊擴散，看最多能擴散多遠。枚舉“中心位置”時間復雜度為 O(N)，從“中心位置”擴散得到“回文子串”的時間復雜度為 O(N)，因此時間復雜度可以降到 O(N^2)。在這里要注意一個細節：回文串在長度為奇數和偶數的時候，“回文中心”的形式是不一樣的。

• 奇數回文串的“中心”是一個具體的字符，例如：回文串 "aba" 的中心是字符 "b"；
• 偶數回文串的“中心”是位于中間的兩個字符的“空隙”，例如：回文串串 "abba" 的中心是兩個 "b" 中間的那個“空隙”。

我們看一下一個字符串可能的回文子串的中心在哪里？我們可以設計一個方法，兼容以上兩種情況：

• 如果傳入重合的索引編碼，進行中心擴散，此時得到的回文子串的長度是奇數；
• 如果傳入相鄰的索引編碼，進行中心擴散，此時得到的回文子串的長度是偶數。

具體編碼細節在以下的代碼的注釋中體現。

public class Solution {public String longestPalindrome(String s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;String res = s.substring(0, 1);// 中心位置枚舉到 len - 2 即可for (int i = 0; i < len - 1; i++) {String oddStr = centerSpread(s, i, i);String evenStr = centerSpread(s, i, i + 1);String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;if (maxLenStr.length() > maxLen) {maxLen = maxLenStr.length();res = maxLenStr;}}return res;}private String centerSpread(String s, int left, int right) {// left = right 的時候，此時回文中心是一個字符，回文串的長度是奇數// right = left + 1 的時候，此時回文中心是一個空隙，回文串的長度是偶數int len = s.length();int i = left;int j = right;while (i >= 0 && j < len) {if (s.charAt(i) == s.charAt(j)) {i--;j++;} else {break;}}// 這里要小心，跳出 while 循環時，恰好滿足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 jreturn s.substring(i + 1, j);} }

總結

以上是生活随笔為你收集整理的回文字符串—回文子串—中心扩散法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。