欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

go语言刷题:5. 最长回文子串

程序员文章站 2022-03-15 22:26:17
...

申明:本文只用做自己学习记录

题目

给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:

输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:

输入:s = “cbbd”
输出:“bb”
示例 3:

输入:s = “a”
输出:“a”
示例 4:

输入:s = “ac”
输出:“a”

代码

//方法1:动态规划
func longestPalindrome(s string) string {
	//字符串总长度
	n := len(s)
	//结果字符串
	result := ""
	//创建二维切片,建立表格,行表示左边界,列表示右边界
	//j(行)表示字符串左边界,i+j(列)表示字符串的右边界
	//因为j<=i+j,所以表格右上方才有用
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}
	//遍历循环,每一个字符串,都往后遍历一次
	for i := 0; i < n; i++ {
		//遍历当前字符串之后的字符
		for j := 0; j+i < n; j++ {
			//边界条件1:当左边界==右边界时,只有1个字符
			if i == 0 {
				//当i==0时,j=i+j
				//即左边界等于右边界
				//为独立子串,属于回文
				dp[j][i+j] = 1
				//边界条件2:当i==1则,[j,i+j]有两个字符
			} else if i == 1 {
				//当左字符==右字符时,属于回文
				if s[j] == s[i+j] {
					dp[j][i+j] = 1
				}
				//边界条件3,当字符数大于2时
			} else {
				//如果左边界字符==右边界字符,则两边向中间移动一位,并赋值为1
				if s[j] == s[i+j] {
					dp[j][i+j] = dp[j+1][i+j-1]
				}
			}
			//边界条件:如果该点大于0,且循环结束
			//则返回当前字符串
			if dp[j][i+j] > 0 && i+1 > len(result) {
				result = s[j : j+i+1]
			}
		}
	}
	return result
}

//方法2:中心字符串法
func longestPalindrome(s string) string {
	//判断边界条件,如果为空字符返回空字符
	if s == "" {
		return ""
	}
	//初始化索引值
	start, end := 0, 0
	//开始遍历
	for i := 0; i < len(s); i++ {
		//奇数回文,以每个字符为中心,向两边索引
		left1, right1 := expandAroundCenter(s, i, i)
		//偶数回文,以两个字符为中心
		left2, right2 := expandAroundCenter(s, i, i+1)
		//更新最大回文数索引值
		if right1-left1 > end-start {
			start, end = left1, right1
		}
		if right2-left2 > end-start {
			start, end = left2, right2
		}
	}
	//返回最长回文字符
	return s[start : end+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
}