[数据结构与算法]java求最长回文子串(时间复杂度O(n^2))

解法：扩展中心法

我们知道回文串一定是对称的，所以我们可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。

这时我们要考虑该回文串以一个字符为中心还是以两个相等的字符为中心，即假设字符串s = “abaabc”，其中既有以'b'为中心的“aba”字符串，还有以“aa"为中心的“baab”字符串。所以我们要考虑n+n-1种情况。

方法代码如下：

public static String longestPalindrome(String s) {
		//如果s长度为0或者不存在，则返回空字符串
		if(s.length() == 0 || s==null) {
			return "";
		} 
		
		int start = 0 , end = 0; //记录最长子回文串的起始位置
		
		for(int i = 0 ; i < s.length() ; i++) {
			int l1 = palindromeLength(s,i,i); //以一个字符为中心
			int l2 = palindromeLength(s,i,i+1); //以两个字符为中心
			int len = Math.max(l1,l2);
			
			//更新回文串
			if((end - start + 1) < len) {
				start = i - (len-1) / 2;
				end = i + len/2;
			}
		}
		return s.substring(start,end+1);//返回最长回文串
	}

public static int palindromeLength(String s, int left, int right) {
		int length = 0; //记录最大回文串长度
		int l = left;  //左
		int r = right;  //右
		//分别向左右搜索，直到左右字符不相等为止
		
		while(l >= 0 && r <= s.length()-1 && s.charAt(l) == s.charAt(r)) {
			l--;
			r++;
		}
		
		length = r - l - 1; //最后一次相等时l和r分别减一和加一，所以长度不是r-l+1
		return length;  //返回长度。
	}

时间复杂度：O(n2）。

空间复杂度：O(1）。

希望能帮到大家。