目录
一、 题目描述
二、 实现思路以及代码
一、 题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
二、 实现思路以及代码
中心扩展法：private int maxString(String s, int left, int right)；返回以S【left...right】为中心的最长回文字符串的长度。
class Solution {public String longestPalindrome(String s) {if(s == null || s.length() == 0){return "";}int len = s.length();int max_length = Integer.MIN_VALUE;HashMap<Integer, String> map = new HashMap<>();for (int i = 0; i < len; i++) {//回文子串中心是一个字符的情况//maxString(String s,int left,int right) : 返回字符串的最长回文子串中相同字符的长度//回文中心是一个字符。例如“..aba..”int nums1 = maxString(s, i - 1, i + 1); //字符串的最长回文子串中相同字符的长度int len1 = nums1 * 2 + 1; // 最长回文字符串的长度//回文中心是两个相同的字符。例如“..baab..” int nums2 = maxString(s, i, i + 1); //字符串的最长回文子串中相同字符的长度int len2 = nums2 * 2; // 最长回文字符串的长度StringBuilder sb = new StringBuilder(); // 借助StringBuilder实现拼接子字符串if (len1 >= len2) {for (int k = i - nums1; k <= i + nums1 ; k++) { // 回文中心是一个字符 if (k >= 0 && k < len) {sb.append(s.charAt(k)); }}} else {for (int k = i - (nums2 - 1) ; k <= i + (nums2); k++) { //回文中心是两个相同的字符if (k >= 0 && k < len) {sb.append(s.charAt(k));}}}max_length = Math.max(Math.max(len1, len2), max_length); // 取两个最长长度的最大值String str = sb.toString(); // sb转换为字符串//做判断，看map中max_length对应的value值的长度是否比str的长度大// 若大则替换，否则不做任何操作if (map.containsKey(max_length)) { //map中存在max_length键if (str.length() > map.get(max_length).length()) {map.put(max_length, str);}} else {//不存在max_length键，添加此键map.put(max_length, str);}sb.delete(0, sb.length()); //StringBuilder重用 清空数据方法}return map.get(max_length);}private int maxString(String s, int left, int right) {int res = 0;int len = s.length();while (left >= 0 && right < len) {// 若回文中心是一个字符c，直接依次判断c两边的字符是否相等,返回相同字符的对数// 若回文中心是两个相同的字符，从中心相同的两个字符开始相两边判断是否相同，返回相同的字符对数if (s.charAt(left) == s.charAt(right)) {left--;right++;res++;} else {break;}}return res;}}动态规划法：
思路：
1、回文字符串中心可以是一个单字符X，也可以是相同的字符XX。在回文字符串中心的两边是对称的的，即回文字符串两边加上相同的字符或者字符串，任然是回文字符串。
2、建立二维数组dp,dp[i][j]表示字符串的子串S[i ... j]是否是回文字符串，boolean类型。
2.1 单个字符为回文字符串，则dp[i][i] = true;
2.2 若s.charAt(i) 与s.charAt(j)相同时，并且子串 S[i+1 ... j-1]是回文串的话，那么S[i .. j]是回文串；若子串 S[i+1 ... j-1]不是回文串的话，那么S[i .. j]不是回文串。
if(s.charAt(i) == s.charAt(j)){if(dp[i+1][j-1]){dp[i][j] = true; }else{dp[i][j] = false;}
}此处需要判断 i+1 与 j-1的关系，只有 i+1 < j+1时，上面的假设成立。反之，不成立。不满足i+1 < j+1 的关系，则说明 下标 i 的下一位是 j 或者 j 的下一位，那么子串S[i .. j]最多只有两个字符。若两个字符s.charAt(i) 与s.charAt(j)相同，则S[i .. j]是回文串，即dp[i][j] = true.
class Solution {public String longestPalindrome(String s) {if(s == null || s.length() == 0){return "";}int len = s.length();boolean[][] dp = new boolean[len][len]; //字符串的子串S[i ... j]是否是回文字符串，boolean类型。true为是回文串for(int i = 0; i< len; i++){//初始化二维数组for(int j = i; j < len; j++){dp[i][j] = false;}dp[i][i] = true;//表示单个字符，是回文串}int max_length = Integer.MIN_VALUE;//回文子串的最大长度String res = "";for(int i = len -1; i >= 0; i--){ //反序迭代 ifor(int j = i; j< len; j++){ //正序迭代 jif(s.charAt(i) == s.charAt(j)){ //两个字符相等if(i+1 <= j-1){if(dp[i+1][j-1] == true){ //子串 S[i+1 ... j-1]是回文串的话，那么S[i .. j]是回文串dp[i][j] = true;}}else{dp[i][j] = true;//s[i .. j]之间最多两个字符，且s.charAt(i) == s.charAt(j) 是回文串}}if(dp[i][j]){//每找到一个回文串，更新最大回文串int length = j-i+1;if(length >=max_length){res = s.substring(i,j+1);max_length = length;}}}}return res;}
}