给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: “babad” 输出:“bab” （注意: “aba” 也是一个有效答案）。 示例 2： 输入: “cbbd” 输出: “bb”。
方法1：暴力法 求一个字符串的最长回文子串，可以将以每个字符为首的子串都遍历一遍，判断是否为回文，如果是回文，再判断最大长度的回文子串。(复杂度太高)
public class Test{ /* 判断是否是回文串（方法1），也可以使用StringBuffer的反转方法，判断反转的和原来的字符串是否相等，相等则为回文串（方法二） */ public boolean isPalindrome(String str){ str = str.toLowerCase(); str = str.replaceAll("[^0-9a-z]",""); int i = 0; int j = str.length()-1; while(i < j){ if(str.charAt(i) == str.charAt(j)){ i++; j--; }else{ return false; } } return true; } public String longestPalindrome(String s) { int len = str.length(); if(len < 2){ return str; } String res = s.subString(0,1); for(int i=0;i<len;i++){ for(int j=i+1; i<len; j++){ String k = s.subString(i,j); if(isPalindrome(k) && k.length() > res.length()){ res = k; } } } return res; } }方法2：动态规划
package algorithm; public class Test{ public String longestPalindrome(String s){ int len = s.length(); if(len < 2){ return s; } boolean[][] dp = new boolean[len][len]; for(int i = 0; i < len; i++){ dp[i][i] = true; } int maxLen = 1; int begin = 0; for(int j = 1; j < len; j++){ for(int i = 0; i < j; i++){ if(s.charAt(i) != s.charAt(j)){ dp[i][j] = false; }else{ if(j-i<3){ dp[i][j] = true; }else{ dp[i][j] = dp[i+1][j-1]; } } if(j-i+1 > maxLen && dp[i][j] == true){ begin = i; maxLen = j-i+1; } } } return s.substring(begin, begin+maxLen); //左闭右开; } public static void main(String[] args){ Test test = new Test(); String s = "bbsdadadsvv"; String res = test.longestPalindrome(s); System.out.println("最长回文子串为:"+res); } } public class Test{ public String longestPalindrome(String s){ int len = s.length(); if(len < 2){ return s; } boolean[][] dp = new boolean[len][len]; for(int i = 0; i < len; i++){ dp[i][i] = true; } int maxLen = 1; int begin = 0; for(int j = 1; j < len; j++){ for(int i = 0; i < j; i++){ dp[i][j] = (s.charAt(i) == s.charAt(j)) && ((j - i < 3) || (dp[i+1][j-1])); //只要dp[i][j]==true成立，就表示子串s[i..j]是回文，此时记录回文长度和起始位置。 if(dp[i][j] == true && j-i+1 > maxLen){ maxLen = j-i+1; begin = i; } } } return s.substring(begin, begin+maxLen); } }（1）状态：dp[i][j]表示子串s[i…j]是否为回文子串 （2）状态转移方程：dp[i][j] = (s[i] == s[j]) and (dp[i+1][j-1]) （3）边界条件：构成区间，j-1 -(i+1) + 1 <2，整理得：j-i<3，即s[i…j]长度为2或者3时，不用检查子串是否回文 利用状态转移方程，每一步的计算都尽可能的利用了之前计算的结果 （4）初始化：单个字符一定是回文串，即dp[i][i] = true （5）输出：在得到一个状态的值为true的时候，记录起始位置和长度，填表完成后再截取 （6）注意边界条件 （7）能用return返回退出，尽量别用break
动态规划实际上在填写一张二维表格，由于i和j的关系是i<=j，所以只填写表的上半部分，这个二维表格记录了求解所有子串的所有状态，每一行表示的是字符串的左边界，每一列表示字符串的右边界，左边界和右边界的组合就唯一确定了一个子串，单个字符一定是回文串，所以先把主对角线上的元素赋值为true；
从状态方程可知，dp[i][j]的值需要参考dp[i+1][j-1]的值，i+1在i得下面，j-1在j得左边，因此参考它左下方的值（利用状态转移方程，每一步的计算都尽可能的利用了之前计算的结果）。 由于这样的关系，在填表的时候，就不能一行行从左向右的填写，应该一列一列的填写，这样保证左下方的值先计算出来，状态转移才是正确的。
