轉(zhuǎn)載地址：https://www.cnblogs.com/clnchanpin/p/6880322.html

假設(shè)一個字符串從左向右寫和從右向左寫是一樣的，這種字符串就叫做palindromic string。如aba,或者abba。本題是這種，給定輸入一個字符串。要求輸出一個子串，使得子串是最長的padromic string。

下邊提供3種思路

1.兩側(cè)比較法

以abba這樣一個字符串為例來看，abba中，一共同擁有偶數(shù)個字。第1位=倒數(shù)第1位。第2位=倒數(shù)第2位......第N位=倒數(shù)第N位
以aba這樣一個字符串為例來看，aba中。一共同擁有奇數(shù)個字符。排除掉正中間的那個字符后，第1位=倒數(shù)第1位......第N位=倒數(shù)第N位
所以，如果找到一個長度為len1的子串后，我們接下去測試它是否滿足，第1位=倒數(shù)第1位。第2位=倒數(shù)第2位......第N位=倒數(shù)第N位。也就是說，去測試從頭尾到中點(diǎn)，字符是否逐一相應(yīng)相等。

public class LongestPalindromicSubString1 {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println(longestPalindrome1("babcbabcbaccba"));}public static String longestPalindrome1(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i < length; i++) {for (int j = i + 1; j < length; j++) {int len = j - i;String curr = s.substring(i, j + 1);if (isPalindrome(curr)) {if (len > maxPalinLength) {longestPalindrome = curr;maxPalinLength = len;}}}}return longestPalindrome;}public static boolean isPalindrome(String s) {for (int i = 0; i < s.length() - 1; i++) {if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {return false;}}return true;} } </span>

?2.動態(tài)規(guī)劃法

如果dp[ i ][ j ]的值為true，表示字符串s中下標(biāo)從 i 到 j 的字符組成的子串是回文串。那么能夠推出：
??? dp[ i ][ j ] = dp[ i + 1][ j - 1] && s[ i ] == s[ j ]。
??? 這是一般的情況，因為須要依靠i+1, j -1，所以有可能 i + 1 = j -1, i +1 = (j - 1) -1，因此須要求出基準(zhǔn)情況才干套用以上的公式：
??? a. i + 1 = j -1，即回文長度為1時，dp[ i ][ i ] = true;
??? b. i +1 = (j - 1) -1，即回文長度為2時，dp[ i ][ i + 1] = （s[ i ] == s[ i + 1]）。
??? 有了以上分析就能夠?qū)懗龃a了。

須要注意的是動態(tài)規(guī)劃須要額外的O(n2)的空間。

public class LongestPalindromicSubString2 {public static String longestPalindrome2(String s) {if (s == null)return null;if(s.length() <=1)return s;int maxLen = 0;String longestStr = null;int length = s.length();int[][] table = new int[length][length];//every single letter is palindromefor (int i = 0; i < length; i++) {table[i][i] = 1;}printTable(table);//e.g. bcba//two consecutive same letters are palindromefor (int i = 0; i <= length - 2; i++) {//System.out.println("i="+i+" "+s.charAt(i));//System.out.println("i="+i+" "+s.charAt(i+1));if (s.charAt(i) == s.charAt(i + 1)){table[i][i + 1] = 1;longestStr = s.substring(i, i + 2);} }System.out.println(longestStr);printTable(table);//condition for calculate whole tablefor (int l = 3; l <= length; l++) {for (int i = 0; i <= length-l; i++) {int j = i + l - 1;if (s.charAt(i) == s.charAt(j)) {table[i][j] = table[i + 1][j - 1];if (table[i][j] == 1 && l > maxLen)longestStr = s.substring(i, j + 1);} else {table[i][j] = 0;}printTable(table);}}return longestStr;}public static void printTable(int[][] x){for(int [] y : x){for(int z: y){//System.out.print(z + " ");}//System.out.println();}//System.out.println("------");}public static void main(String[] args) {System.out.println(longestPalindrome2("1263625"));//babcbabcbaccba} }</span>

3.中心擴(kuò)展法

由于回文字符串是以中心軸對稱的，所以假設(shè)我們從下標(biāo) i 出發(fā)。用2個指針向 i 的兩邊擴(kuò)展推斷是否相等，那么僅僅須要對0到
n-1的下標(biāo)都做此操作，就能夠求出最長的回文子串。但須要注意的是，回文字符串有奇偶對稱之分，即"abcba"與"abba"2種類型。
因此須要在代碼編寫時都做推斷。
???? 設(shè)函數(shù)int Palindromic ( string &s, int i ,int j) 是求由下標(biāo) i 和 j 向兩邊擴(kuò)展的回文串的長度，那么對0至n-1的下標(biāo)。調(diào)用2次此函數(shù)：
???? int lenOdd =? Palindromic( str, i, i ) 和 int lenEven = Palindromic (str , i , j )，就可以求得以i 下標(biāo)為奇回文和偶回文的子串長度。

???? 接下來以lenOdd和lenEven中的最大值與當(dāng)前最大值max比較就可以。
???? 這種方法有一個優(yōu)點(diǎn)是時間復(fù)雜度為O(n2)，且不須要使用額外的空間。

public class LongestPalindromicSubString3 {public static String longestPalindrome(String s) {if (s.isEmpty()) {return null;}if (s.length() == 1) {return s;}String longest = s.substring(0, 1);for (int i = 0; i < s.length(); i++) {// get longest palindrome with center of iString tmp = helper(s, i, i);if (tmp.length() > longest.length()) {longest = tmp;}// get longest palindrome with center of i, i+1tmp = helper(s, i, i + 1);if (tmp.length() > longest.length()) {longest = tmp;}}return longest;}// Given a center, either one letter or two letter,// Find longest palindromepublic static String helper(String s, int begin, int end) {while (begin >= 0 && end <= s.length() - 1&& s.charAt(begin) == s.charAt(end)) {begin--;end++;}String subS = s.substring(begin + 1, end);return subS;}public static void main(String[] args) {System.out.println(longestPalindrome("ABCCBA"));//babcbabcbaccba} }</span>

轉(zhuǎn)載于:https://www.cnblogs.com/yanhowever/p/9930184.html

總結(jié)

以上是生活随笔為你收集整理的转载-----Java Longest Palindromic Substring(最长回文字符串)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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