题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2：

输入: “cbbd” 输出: “bb”

动态规划 时间O(N^2) 空间O(N^2)

class Solution { public String longestPalindrome(String s) { int len = s.length(); if(len <1 || s == null) return ""; boolean[][] dp = new boolean[len][len]; int left =-1,right =-1; for(int i=0;i < len;i++){ dp[i][i]=true; } int maxLen = -1; for(int i=len-1;i>=0;i--){ for(int j=i+1;j<len;j++){ if(s.charAt(i)==s.charAt(j) ){ if(j-i==1) dp[i][j]=true; else dp[i][j]=dp[i+1][j-1]; }else{dp[i][j] = false;} if(dp[i][j] && maxLen < j-i){ left =i; right =j; maxLen = j-i; } } } if(maxLen ==-1) return s.substring(0, 1); return s.substring(left, right+1); } }

中心扩散 时间O(N^2) 空间O(1)

public class Solution { public String longestPalindrome(String s) { int len = s.length(); if (len < 2) { return s; } int maxLen = 1; String res = s.substring(0, 1); // 中心位置枚举到 len - 2 即可 for (int i = 0; i < len - 1; i++) { String oddStr = centerSpread(s, i, i); String evenStr = centerSpread(s, i, i + 1); String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr; if (maxLenStr.length() > maxLen) { maxLen = maxLenStr.length(); res = maxLenStr; } } return res; } private String centerSpread(String s, int left, int right) { // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数 // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数 int len = s.length(); int i = left; int j = right; while (i >= 0 && j < len) { if (s.charAt(i) == s.charAt(j)) { i--; j++; } else { break; } } // 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j return s.substring(i + 1, j); } }