求解最长回文子串的几种方法（Java版）

LeetCode 5 给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成

解法一、暴力解法

作为一个小菜鸡，这是我做题最容易想到的方法，就是找出每个字符串，判断是否是回文串，记录最长的子串返回即可。这种方法很容易想到，但是时间复杂度为O(n³)，会超出时间限制。

//暴力解法
class Solution {
	public String longestPalindrome(String s) {
		//长度为1的字符串的单独考虑
     	if(s.length()==1)  return s;
    	int maxlength=0;
     	String ans="";
     	for(int i=0;i<s.length()-1;i++){
     		//注意j<=s.length()，因为substring(i,j) 截取的字符串区间是前闭后开的，即[i,j)
         	for(int j=i+1;j<=s.length();j++){		
             	String temp=s.substring(i,j);
            	if(isPalindrome(temp)&&temp.length()>maxlength){
                	ans=temp;
                	maxlength=ans.length();
            	}
         	}
    	}
     	return ans;
	}
	//判断是否是回文串的函数
	public boolean isPalindrome(String s){
    	int length=s.length();
    	for(int i=0;i<length/2;i++){
        	if(s.charAt(i)!=s.charAt(length-i-1))
            	return false;
    	}
    	return true;
	}
}

方法二、中心扩展法

回文串的最大的特点就是左右对称，所以，我们可以选定一个中心，每次循环往左右各扩展一位，只要左右这两个字符相等，那么它就是回文串。需要注意的是，偶数长度的回文串中心是最中间的两个字符，要把这两个字符作为中心扩展。

//中心扩散法
class Solution {
	public String longestPalindrome(String s) {
    	int length=s.length();
    	int start=0;
    	int end=0;
    	for(int i=0;i<length;i++){
        	int odd=getLength(s,i,i);
        	int even=getLength(s,i,i+1);
        	int temp=odd>even ? odd : even ;
        	//求出最长回文串的起始和终止位置，注意start与end的计算方法
        	if(temp>end-start){
            	start=i-(temp-1)/2;
            	end=i+temp/2;
        	}
    	}
    	return s.substring(start,end+1);
	}
	public int getLength(String s,int left,int right){
    	while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
        	left--;
        	right++;
    	}
    	//注意回文串长度的计算right-left+1-2
    	return right-left-1;
	}
}

方法三、动态规划

动态规划就是一种利用空间换时间的办法，设置一个二维布尔数组temp[][]，假设temp[i][j]表示s[i]~s[j]为回文串，那么，temp[i][j]=true等价于temp[i+1][j-1]=true&&s[i]=s[j]，例如"bab"为回文串，那么"#bab#"肯定也是回文串。对于temp的初始化就是一个字符肯定是回文串、两个相等的字符也是回文串。

class Solution {
	public String longestPalindrome(String s) {
    	int length=s.length();
    	if(length==1) {
        	return s;
    	} 
    	boolean[][] temp=new boolean[length][length];
    	int start=0;
    	int maxlength=1;
    	//temp初始化
   	 	for(int i=0;i<length;i++){
        	//一个字符肯定是回文
        	temp[i][i]=true;
        	//两个相等字符的也是回文
        	if(i<length-1&&s.charAt(i)==s.charAt(i+1)) {
            	temp[i][i+1]=true;
            	start=i;
            	maxlength=2;
        	}
    	}
    	//len表示回文串长度，len=3表示从长度为3的开始找起
    	for(int len=3;len<=length;len++){
        	//i表示字符串的起始位置，注意for循环条件防止越界
        	for(int i=0;len+i-1<length;i++){
            	//loc表示终止位置
            	int loc=i+len-1;
            	if(s.charAt(i)==s.charAt(loc)&&temp[i+1][loc-1]){
                	temp[i][loc]=true;
                }
            	if(temp[i][loc]&&len>maxlength){
                	start=i;
                	maxlength=len;
            	}
        	}
   	 	}
    	return s.substring(start,start+maxlength);
	}
}