最长回文子串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;imaxlength){
                	ans=temp;
                	maxlength=ans.length();
            	}
         	}
    	}
     	return ans;
	}
	//判断是否是回文串的函数
	public boolean isPalindrome(String s){
    	int length=s.length();
    	for(int i=0;i 
方法二、中心扩展法 
回文串的最大的特点就是左右对称，所以，我们可以选定一个中心，每次循环往左右各扩展一位，只要左右这两个字符相等，那么它就是回文串。需要注意的是，偶数长度的回文串中心是最中间的两个字符，要把这两个字符作为中心扩展。
 
//中心扩散法
class Solution {
	public String longestPalindrome(String s) {
    	int length=s.length();
    	int start=0;
    	int end=0;
    	for(int i=0;ieven ? 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 
方法三、动态规划 
动态规划就是一种利用空间换时间的办法，设置一个二维布尔数组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;imaxlength){
                	start=i;
                	maxlength=len;
            	}
        	}
   	 	}
    	return s.substring(start,start+maxlength);
	}
}

                
                
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！