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
}