題目描述

描述：

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

示例 1：

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

示例 2：

輸入: “cbbd”
輸出: “bb”

普通暴力

分析：

• 求最長的回文串。而回文串又有奇數串和偶數串兩種形式，我們只需要對有所情況從左到右進行枚舉，然后返回最長的串即可。
• 在編寫代碼的同時注意邊界的問題不能越界。返回合理編號字符串。
• 不要用String類型進行拼湊，因為String是不可變類每個拼湊都會生成一個新的字符串，多個拼湊會導致效率非常低下。

通過代碼：

public String longestPalindrome(String s) {int max = 0;String va = "";if (s.length() > 0)va = s.charAt(0) + "";for (int i = 0; i < s.length() - 1; i++) {int l = i, r = i;//奇數個回文串while (l >= 0 && r <= s.length() - 1) {if (s.charAt(l) == s.charAt(r)) {l--;r++;} else {break;}}if (r - l + 1 > max) {max = r - l + 1;va = s.substring(l+1, r );}l = i;r = i + 1;//偶數個回文串if (s.charAt(i) == s.charAt(i + 1)) {while (l >= 0 && r <= s.length() - 1) {if (s.charAt(l) == s.charAt(r)) {l--;r++;} else {break;}}}if (r - l + 1 > max) {max = r - l + 1;va = s.substring(l+1, r );}}return va;}

中心擴散

求最長回文串，能不能有什么優化的方案呢？

首先，最長可能出現在哪里呢？

• 當然最長會出現在中間位置：

如果第一次就找到這個最大的長度了，那么還需要查找其他不可能比它長的回文串了嘛？

• 當然不需要。

使用什么方法能夠確定不需要再查找更短的回文串了呢？

• 從中間向兩邊查找，邊查找邊標記最大的回文串長度為max。
• 如果向兩邊擴散時候該點到其中一個邊界距離的二倍明顯已經小于最長回文串的max長度，那就沒必要計算了。可以直接停止。

不過在具體的代碼實現方面，要注意一些界限、特殊情況。ac代碼為：

// 法二，中間擴散public static String getmaxhuiwen(int l,int r,String s) {if(l>r)return"";while (l >= 0 && r <= s.length() - 1) {if (s.charAt(l) == s.charAt(r)) {l--;r++;} else {break;}}return s.substring(l+1, r);}public static String longestPalindrome(String s) {int max = 0;String va = "";if(s.length()<2)return s;//""和"a"int mid = (s.length()-1) / 2;//中間(偶數左側，奇數中間)for (int i = 0; i < mid+1; i++) {int l = mid - i, r = l;//左奇數個String s1=getmaxhuiwen(l, r, s);va=va.length()>s1.length()?va:s1;l=mid-i;r=l+1;//左偶數個s1=getmaxhuiwen(l, r, s);va=va.length()>s1.length()?va:s1;l=mid+i;r=l;//右奇數個s1=getmaxhuiwen(l, r, s);va=va.length()>s1.length()?va:s1;l=mid+i;r=l+1;//右偶數個s1=getmaxhuiwen(l, r, s);va=va.length()>s1.length()?va:s1;max=va.length();//最大回文長度if(max>(mid-i+1)*2)//找不到更長直接返回{break;}}return va;}

這種情況效率已經不錯了：

結語

至于題解區有人提出動態規劃的方法，但是動態規劃在這題并沒有太好的效率提高。這里就不作介紹了。

還有求回文串的馬拉車算法，后面會專門寫一篇記錄學習和理解，敬請關注！

最后我請你們兩連事幫忙一下:

點贊、關注一下支持， 您的肯定是我在平臺創作的源源動力。

微信搜索「bigsai」，關注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術。加我還可拉你進力扣打卡群一起打卡LeetCode。

記得關注、咱們下次再見！

總結

以上是生活随笔為你收集整理的LeetCode 05最长回文子串的全部內容，希望文章能夠幫你解決所遇到的問題。

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