一.题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
示例 3：
输入：s = “a”
输出：“a”
示例 4：
输入：s = “ac”
输出：“a”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
二.题目解析
1.暴力法
public String longestPalindrome(String s) {
/*暴力法，时间复杂度O(n^3),空间复杂度O(1)
* */
if(s == null || s.length() == 0){
return null;
}
int i,j,max = 0;
String res = null;
for (i = 0; i < s.length(); i++) {
for (j = i; j < s.length(); j++) {
//如果不满足j - i + 1 > max就不会进行isPalindrome函数的判断了
if(j - i + 1 > max && isPalindrome(s,i,j)){
max = j - i + 1;
res = s.substring(i,j + 1);
}
}
}
return res;
}
private Boolean isPalindrome(String s,int start,int end){
if(start == end){
return true;
}
int i = start,j = end;
while (i <= j){
if(s.charAt(i) != s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
2.动态规划
public String longestPalindrome(String s) {
/*动态规划,时间复杂度O(n^2),空间复杂度O(n^2)
* */
if (s == null || s.length() < 2) {
return s;
}
int strLen = s.length();
int maxStart = 0; //最长回文串的起点
int maxEnd = 0; //最长回文串的终点
int maxLen = 1; //最长回文串的长度
//定义状态：dp[i][j]表示从i到j的字符串是否是回文子串，dp数组初始状态全是false
boolean[][] dp = new boolean[strLen][strLen];
for (int r = 1; r < strLen; r++) {
for (int l = 0; l < r; l++) {
//状态转移方程，dp[l,r] = (s.charAt(l) == s.charAt(r) && dp[l + 1][r - 1])
//这里r-l <=2就是dp的初始状态，因为dp数组初始状态全是false。
// 当子串 s[i..j]的长度等于2或者等于3的时候，s[i..j] 是否是回文由 s[i] 与 s[j] 是否相等决定。
if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
dp[l][r] = true;
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
maxStart = l;
maxEnd = r;
}
}
}
}
return s.substring(maxStart, maxEnd + 1);
}
3.中心扩散法
public String longestPalindrome1(String s) {
/*中心扩散法，从某个位置出发，向两边扩散
时间复杂度O(n^2),空间复杂度O(1)
* */
if(s == null || s.length() == 0){
return null;
}
int pre,last,max = 0,finalPre = 0,finalLast = 0;
char cur;
String res = null;
for (int i = 0; i < s.length(); i++) {
//假设以i位置元素开始向左右扩散
cur = s.charAt(i);
pre = i - 1;
last = i + 1;
//与cur相等的这段字符串自成回文
while (pre >= 0 && s.charAt(pre) == cur){
pre--;
}
while (last < s.length() && s.charAt(last) == cur){
last++;
}
//从区间左右分别扩散，直到pre和last指向元素不相等
while (pre >= 0 && last < s.length() && s.charAt(pre) == s.charAt(last)){
pre--;
last++;
}
//更新最大回文子串的值，last - 1 - (pre + 1)
if(last - 1 - pre > max){
max = last - pre - 1;
finalPre = pre + 1;//由于需要返回字符串故还需要记录位置
finalLast = last - 1;
}
}
res = s.substring(finalPre,finalLast + 1);
return res;
}
4.中心扩散法另一版本
参考来源：
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/chao-jian-dan-de-zhong-xin-kuo-san-fa-yi-qini/
class Solution {
String ans = "";
public String longestPalindrome(String s) {
for (int i = 0; i < s.length(); i++) {
// 回文子串长度是奇数,最中间是同一个数,所以取一个就行
helper(i, i, s);
// 回文子串长度是偶数,取两个数字
helper(i, i + 1, s);
}
return ans;
}
public void helper(int m, int n, String s) {
while (m >= 0 && n < s.length() && s.charAt(m) == s.charAt(n)) {
m--;
n++;
}
// 注意此处m,n的值循环完后 是恰好不满足循环条件的时刻
// 此时m到n的距离为n-m+1，但是mn两个边界不能取 所以应该取m+1到n-1的区间 长度是n-m-1
if (n - m - 1 > ans.length()) {
//substring要取[m+1,n-1]这个区间
//end处的值不取,所以下面写的是n不是n-1
ans = s.substring(m + 1, n);
}
}
}
