最长的回文子串 - 中等 - 算法题 - 算法 - 计算机

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

示例 1：

示例 2：

	输入：s = "cbbd"
	输出："bb"

提示：

题解

中心扩散法

	/**
	* bacabab
	* 枚举每一个字符，到达 c 时，校验 bacab
	*/
	class Solution {
	public String longestPalindrome(String s) {

	int length = s.length();
	char[] array = s.toCharArray();
	String result = s.substring(0, 1);

	// 枚举每一个字符，每一个字符都为中间点
	for (int i = 0; i < length - 1; i++){
	// 找出当前最长的回文子串，列如 aba
	String p1 = isPalindrome(i, i, array, s);
	if (result.length() < p1.length()){
	result = p1;
	}

	// 找出当前最长的回文子串，列如 abba
	String p2 = isPalindrome(i, i + 1, array, s);
	if (result.length() < p2.length()){
	result = p2;
	}
	}

	return result;

	}

	private String isPalindrome(int left, int right, char[] array, String s) {
	// 当越界时，结束
	while (left >= 0 && right < array.length){
	// 如果当前左字符与右字符不等时，返回当前回文子串
	if (array[left] != array[right]) return s.substring(left + 1, right);


	left--;
	right++;
	}

	// 返回最长的回文子串
	return s.substring(left + 1, right);
	}

	}

优化

	/**
	* 中心扩散法
	*/
	public class Solution {

	public String longestPalindrome(String s) {
	int length = s.length();
	char[] array = s.toCharArray();
	int start = 0, end = 0;

	// 枚举每一个字符，每一个字符都为中间点
	for (int i = 0; i < length - 1; i++) {
	int len1 = expandAroundCenter(array, i, i);
	int len2 = expandAroundCenter(array, i, i + 1);

	int len = Math.max(len1, len2);

	if (len > end - start){
	start = i - (len - 1) / 2;
	end = i + len / 2;
	}
	}

	return s.substring(start, end + 1);
	}

	public int expandAroundCenter(char[] array, int left, int right) {
	while (left >= 0 && right < array.length && array[left] == array[right]){
	left--;
	right++;
	}
	return right - left - 1;
	}
	}

动态规划

	/**
	* 动态规划
	*/
	class Solution {
	public String longestPalindrome(String s) {

	int length = s.length();
	char[] array = s.toCharArray();

	//dp [i][j] 表示 s [i..j] 是否是回文串
	boolean[][] dp = new boolean[length][length];
	// 初始化：所有长度为 1 的子串都是回文串
	for (int i = 0; i < length; i++){
	for (int j = 0; j < length; j++) {
	dp[i][j] = true;
	}
	}

	int maxLength = 1;
	int start = 0;
	// 先枚举子串长度
	for (int l = 2; l <= length; l++){
	// 枚举左边界，左边界的上限设置可以宽松一些
	for (int i = 0; i < length; i++){
	// 由 l 和 i 可以确定右边界，即 j - i + 1 = l 得
	int j = l + i - 1;
	// 如果右边界越界，就可以退出当前循环
	if (j >= length) break;

	if (array[i] != array[j]){
	dp[i][j] = false;
	}else if (j - i < 3){
	dp[i][j] = true;
	}else {
	dp[i][j] = dp[i + 1][j - 1];
	}
	// 只要 dp [i][L] == true 成立，就表示子串 s [i..L] 是回文，此时记录回文长度和起始位置
	if (dp[i][j] && j - i + 1 > maxLength){
	maxLength = j - i + 1;
	start = i;
	}

	}

	}

	return s.substring(start, start + maxLength);

	}
	}

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring