最长的回文子串–题解

题目描述

该题为leetcode的第五题

给定一个字符串，让我们找出其中最长的回文子串。

题目解析

其实这道题的做法很多种：

暴力解法：这是最简单的解决方法，我们只需要将所有的子串列出来，然后找出其中所有的子串，判断是否为回文子串，并且找出其中最大值。我尝试了一下leetcode给了我超时，效率可想而知（手动狗头
动态规划：这道题也可以使用动态规划的思想，P*(i,j)为i到j是否是回文子串。状态转移方程式：P*(i,j)=P(i+1,j−1)∧(S**i==S**j)，最后提交效率也并不高，动态规划的解题方法可以去参考一下官方题解，这里主要讲解下一个解题方法
中心扩散：遍历字符串，每一个元素都向外扩散，找到每一个元素向外扩散最长的回文子串然后记录一下，最后返回即可，但是有几点需要特别注意：当前后元素相同时需要特别注意，将前后两个元素当作中心向外扩散即可；记录每一个最长子串时用拷贝的方式会造成很大的消耗，我们可以记录每个回文子串的索引，最后函数返回时在进行拷贝

中心扩散–golang实现

func longestPalindrome(s string) string {
	//双指针，中心扩散法
	//字符串为空时返回空
	if s == "" {
		return ""
	}
	//最终结果开始的指针
	startIndex := 0
	//最终结果结束的指针
	endIndex :=0
	//从头遍历字符串
	for i := 0; i < len(s);i++ {
		//第一种情况：假设当前位置前后没有重复元素
		//从i开始向两边扩散，返回从i开始扩散后子串的left与right坐标
		left, right := expandAroundCenter(s, i, i)
		//第二种情况：假设i后一个元素为重复元素，将i与i+1元素为中心向外扩散
		//注意：如果i+1个元素与i元素不相同会返回i的坐标left为i right也为i
		left2, right2 := expandAroundCenter(s, i, i+1)
		//判断第一种情况子串的长度是否比当前最大子串的长度大，如果是覆盖
		if right-left>endIndex-startIndex {
			startIndex,endIndex = left,right
		}
		//判断第二种情况子串的长度是否比当前最大子串的长度大，如果是覆盖
		if right2-left2>endIndex-startIndex {
			startIndex,endIndex = left2,right2
		}
	}
	return s[startIndex:endIndex+1]
}
//扩散
func expandAroundCenter(s string, left, right int) (int, int) {
	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1 , right+1 { }
	return left + 1, right - 1
}