回文字符串，是指正讀和倒讀的結果一樣的字符串，從結構上來看，兩側的字符呈中心對稱。在漢語中，有很多有趣的迴文詩詞，回文對聯熟語，比如「響水池中池水響，黃金谷裡谷金黃」、「霧鎖山頭山鎖霧，天連水尾水連天」等。根據其結構特徵，我們很容易設計出一個判斷字符串是否回文的算法：
isPalindromic(s)boolean flag=truechar[] chars=s.toCharArray()for i=0 to (chars.length-1)/2if chars[i]!=chars[chars.length-1-i] flag=false breakreturn flag
現在我們看一道leetcode中關於取一個字符串中最長的回文字的問題：
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
首先最簡單的方法，暴力窮舉所有的子串，然後分別利用上述的方法進行判斷即可。遍歷+判斷，窮舉法總的時間複雜度為O(n^3).
bruteForceForPalindromic(S)String resultfor i=0 to s.length()-1for j=i+1 to s.length()-1 substring=s.substring(i,j) if(isPalindromic(substring) and substring.length()<result.length()) result=substring
很顯然，上述暴力算法在運行效率上是極低的。主要原因是其存在著大量重複的判斷，比如當substring(i,j)不是回文串時，我們可以確定substring(i-1,j+1)一定不是回文串，不用進行判斷即可。由此我們考慮構造一個從中心節點雙向探測的方法來獲取最長的回文子串，即判斷每一個中心節點可以構成的回文的最長串。現在的主要問題是，一共有多少個這樣的中心節點呢？答案是2*n-1個，這是考慮了奇數回文和偶數回文的兩種不同情況，如下圖所示。
/*** 以每一個點為中心點，向兩邊探測的方法判斷回文 * @param s * @return */ private static String getLongestPalindromic1(String s) { String result = ""; String sub = ""; char[] chars = s.toCharArray(); int n = s.length(); int j = 0; //以此以每一個字符作為回文的中心節點centercode for (int i = 0; i < n; i++) { //奇數回文探測 j = 0; while (j <= i && i + j < n && chars[i - j] == chars[i + j]) { sub = s.substring(i - j, i + j + 1); j++; } result = result.length() < sub.length() ? sub : result; //偶數回文探測 j = 0; while (j <= i && i + j + 1 < n && chars[i - j] == chars[i + j + 1]) { sub = s.substring(i - j, i + j + 2); j++; } result = result.length() < sub.length() ? sub : result; } return result; }
對於當個字符來說，其本身認為是回文的，則可以得到dptablei=true;
最後我們考慮動態規劃的基礎值的情況：
首先我們使用一個布爾類型的二維數組dptablen來表徵第i個字符到底j個字符構成的子串是否回文，構成則值為true，否則為false。考慮到對於回文子串substring(i+1,j-1)若且唯若s[i]==[j]時，可以得到substring(i,j)是回文的。現在可以根據這樣的性質去構造遞推關係：
對於當個字符來說，其本身認為是回文的，則可以得到dptablei=true;
對於相鄰的兩個字符來說，如果兩個字符是相等的，則認為其是回文的，否則不構成回文，所以dptablei=s[i]==s[i+1]。
綜合上述的討論，算法的時間複雜度為O(n^2)。Java實現如下：
/*** 動態規劃的方法求解最長回文子串 * @param s * @return */ private static String getLongestPalindromicDP(String s) { String result = ""; char[] chars = s.toCharArray(); int n = chars.length; boolean[][] dptable = new boolean[n][n]; //初始化動態規劃數組 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dptable[i][j] = false; } } //設置規劃的base值 for (int i = 0; i < n; i++) { dptable[i][i] = true; } for (int i = 0; i < n - 1; i++) { if (chars[i] == chars[i + 1]) { dptable[i][i + 1] = true; } } //規劃計算 for (int j = 2; j < n; j++) { for (int i = 0; i < j - 1; i++) { dptable[i][j] = dptable[i + 1][j - 1] && (chars[i] == chars[j]); } } //取得最長的回文串 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dptable[i][j] == true) { result = result.length() <= j - i ? s.substring(i, j + 1) : result; } } } return result; }