给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
解法一:
中心扩散法
$O(1)$
$O(n2)$
func longestPalindrome(s string) string {
if len(s) <= 1 {
return s
}
max := 0
ans := ""
for i := 0; i < 2 * len(s) - 1; i++ {
k := i
j := i
for ; j >= 0 && k < 2 * len(s) - 1; {
if s[j / 2] == s[k / 2] {
if (k / 2) - (j / 2) >= max {
max = (k / 2) - (j / 2)
ans = s[(j / 2) : (k / 2) + 1]
}
} else {
break
}
if j % 2 == 0 {
j -= 2
k += 2
} else {
j -= 1
k += 1
}
}
}
return ans
}
解法二:
动态规划
$O(n2)$
$O(n2)$
//动态规划
func longestPalindrome(s string) string {
if len(s) <= 1 {
return s
}
if len(s) == 2 && s[0] == s[1] {
return s
} else if len(s) == 2 {
return string(s[0])
}
max := 0
ans := string(s[0])
var dp [1005][1005]bool
for i := 1; i < len(s); i++ {
for j := 0; j < i; j++ {
if s[i] == s[j] && (i - j <= 2 || (dp[j + 1][i - 1])) {
dp[j][i] = true
if (i - j) >= max {
max = i - j
ans = s[j : i + 1]
}
}
}
}
return ans
}
解法三:
马拉车算法
$O(n)$
$O(n)$
func add(s string) string {
ans := "#"
for i := 0; i < len(s); i++ {
ans += s[i:i+1]
ans += "#"
}
return ans
}
//马拉车算法
func longestPalindrome(s string) string {
s = add(s)
r := 0
id := 0
maxLen := 0
rightIndex := 0
p := [10005]int{0}
for i := 0; i < len(s); i++ {
if r > i {
tmp := p[2 * id - i]
if r - i < tmp {
tmp = r - i
}
p[i] = tmp
} else {
p[i] = 1
}
for i - p[i] >= 0 && i + p[i] < len(s) && s[i - p[i]] == s[i + p[i]] {
p[i]++
}
if p[i] + i > r {
r = p[i] + i
id = i
}
if p[i] - 1 > maxLen {
maxLen = p[i] - 1
rightIndex = i
}
}
fmt.Printf("maxLen = %d, rightIndex = %d, ans = %s\n", maxLen, rightIndex, s[rightIndex - maxLen : rightIndex + maxLen])
ans := s[rightIndex - maxLen : rightIndex + maxLen]
for i := 0; i < len(ans); i++ {
if ans[i] == '#' {
ans = ans[:i] + ans[i + 1:]
}
}
return ans
}
最近由于刚入职的原因,要学习的东西比较多,好久都没有更新了,以后尽量保证每周做一道题。