LeetCode---5. Longest Palindromic Substring（最长回文子串）

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Subscribe to see which companies asked this question

public class Solution{
public  String longestPalindrome(String s) {
	if (s.isEmpty()) {
		return null;
	}
 
	if (s.length() == 1) {
		return s;
	}
 
	String longest = s.substring(0, 1);
	for (int i = 0; i < s.length(); i++) {
		// get longest palindrome with center of i
		String tmp = helper(s, i, i);
		if (tmp.length() > longest.length()) {
			longest = tmp;
		}
 
		// get longest palindrome with center of i, i+1
		tmp = helper(s, i, i + 1);
		if (tmp.length() > longest.length()) {
			longest = tmp;
		}
	}
 
	return longest;
}
           

public String helper(String s, int begin, int end) {
<span style="white-space:pre">	</span>while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
<span style="white-space:pre">		</span>begin--;
<span style="white-space:pre">		</span>end++;
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>return s.substring(begin + 1, end);
}
           

Manacher算法:

时间超时：

public class Solution {
    public String longestPalindrome(String s) {
        		int id=1;//回文中心,
		int[] r;//记录以i为中心的最大半径
		int mx=1;//记录最大回文边界
		String ss="$#";
		//1.奇偶性处理
		for(int i=0;i<s.length();i++){
			ss+=s.charAt(i);
			ss+="#";
		}
		//2.
		int max=0,ii=0;
		r=new int[ss.length()];
		for(int i=1;i<ss.length();i++){
			if(i<mx){r[i]=Math.min(r[2*id-i], mx-i);}else{r[i]=1;} //算法核心

			try{while(ss.charAt(i-r[i])==ss.charAt(i+r[i])){r[i]++;}}
			catch(Exception e){}
			if(r[i]+i>mx){mx=r[i]+i;id=i;}
			if(r[i]>max){max=r[i];ii=i;}
					
			
		}
		//3.找出最大的半径

		ss=ss.substring(ii-max+1, ii+max);
		String sss="";
		for(int i=0;i<ss.length();i++){
			if(ss.charAt(i)!='#'){sss+=ss.charAt(i);}
		}
		return sss;
    }
}