?

?

暴力解法:

? ?列舉所有的子串，判斷是否為回文串,保存最長的回文串。

/** 暴力解法: 列舉所有的子串，判斷是否為回文串,保存最長的回文串。*/public int getLongestPalindrome(String A, int n) {if(n == 0 || n == 1)return n;int count = 0;String temp;for (int i = 0; i < n; i++) {for (int j = i+1; j <= n; j++) {// 截取字符串temp = A.substring(i,j);// 判斷字符串是否為回文if(isPalindrome(temp) && (j-i) > count){count = j-i;}}}return count;}private boolean isPalindrome(String str){int start=0;int end=str.length()-1;while(start<end){if(str.charAt(start) == str.charAt(end)){start++;end--;}else{return false;}}return true;}

?

動態(tài)規(guī)劃(利用已有的信息，判斷下一步)

? 暴力解法時間復(fù)雜度太高，我們可以考慮，去掉一些暴力解法中重復(fù)的判斷。

? 首先定義：字符串 s 從下標(biāo) i 到下標(biāo) j 的字串為 P(i, j)，若 s 從下標(biāo) i 到下標(biāo) j 的字串為回文串，則 P(i, j) = true，否則?P(i, j) = false。如下圖所示：

? 則 P(i, j) = (P(i + 1, j - 1) && s[i] == s[j])。

? 所以如果我們想知道 P（i,j）的情況，不需要調(diào)用判斷回文串的函數(shù)了，只需要知道 P（i+1，j?1）的情況就可以了，這樣時間復(fù)雜度就少了?O(n)。因此我們可以用動態(tài)規(guī)劃的方法，空間換時間，把已經(jīng)求出的 P（i，j）存儲起來。

? 如果 s[i+1, j-1] 是回文串，那么只要 s[i] == s[j]，就可以確定 s[i, j] 也是回文串了。

注意：

? 求 長度為 1?和長度為 2?的 P(i, j) 時不能用上邊的公式，因為我們代入公式后會遇到 P[i][j] 中 i > j 的情況，比如求P[1][2] 的話，我們需要知道 P[1+1][2-1]=P[2][1] ，而 P[2][1] 代表著 S[2, 1] 是不是回文串，這顯然是不對的，所以我們需要單獨判斷。

? 所以我們先初始化長度是 1 的回文串的 P [i , j]，這樣利用上邊提出的公式 P(i,j)=(P(i+1,j-1) && S[i]==S[j])，然后兩邊向外各擴充一個字符，長度為 3?的，為 5?的，所有奇數(shù)長度的就都求出來了。同理，初始化長度是 2 的回文串 P[i,i+1]，利用公式，長度為 4?的，6?的所有偶數(shù)長度的就都求出來了。
?

?

public int getLongestPalindrome(String A, int n) {int sLen = n;int maxLen = 0;String ans = "";boolean[][] P = new boolean[sLen][sLen];// 遍歷所有長度 "abc1234321"for (int len = 1; len <= sLen; len++) {for (int start = 0; start < sLen; start++) {int end = start + len - 1;// 下標(biāo)越界，結(jié)束循環(huán)if (end >=sLen) {break;}P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1]) && A.charAt(start) == A.charAt(end);if (P[start][end] && len > maxLen) {maxLen = len;ans = A.substring(start, end + 1);}}}return ans.length();}

?

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的常考数据结构与算法:最长回文子串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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