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

解答參考：動態(tài)規(guī)劃、中心擴(kuò)散、Manacher 算法

問題描述：

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

算法思路：

本題可以采用暴力破解法、中心擴(kuò)散法、Manacher算法3種方法，本篇文章講解暴力破解法。根據(jù)回文子串的定義，枚舉所有長度大于等于 2?的子串，依次判斷它們是否是回文；

在具體實現(xiàn)時，可以只針對大于“當(dāng)前得到的最長回文子串長度”的子串進(jìn)行“回文驗證”；

在記錄最長回文子串的時候，可以只記錄“當(dāng)前子串的起始位置”和“子串長度”，不必做截取。這一步我們放在后面的方法中實現(xiàn)。

說明：暴力解法時間復(fù)雜度高，但是思路清晰、編寫簡單。由于編寫正確性的可能性很大，可以使用暴力匹配算法檢驗我們編寫的其它算法是否正確。優(yōu)化的解法在很多時候，是基于“暴力解法”，以空間換時間得到的，因此思考清楚暴力解法，分析其缺點，很多時候能為我們打開思路。

public class Solution {public String longestPalindrome(String s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;// s.charAt(i) 每次都會檢查數(shù)組下標(biāo)越界，因此先轉(zhuǎn)換成字符數(shù)組char[] charArray = s.toCharArray();// 枚舉所有長度大于 1 的子串 charArray[i..j]for (int i = 0; i < len - 1; i++) {for (int j = i + 1; j < len; j++) {if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);}/*** 驗證子串 s[left..right] 是否為回文串*/private boolean validPalindromic(char[] charArray, int left, int right) {while (left < right) {if (charArray[left] != charArray[right]) {return false;}left++;right--;}return true;} }

總結(jié)

以上是生活随笔為你收集整理的回文字符串—回文子串—暴力破解法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。