java求最长回文子串(时间复杂度O(n^2))

本文主要是介绍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(n²）。

空间复杂度：O(1）。

希望能帮到大家。

这篇关于java求最长回文子串(时间复杂度O(n^2))的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！