mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-07 09:54:57 +08:00
118 lines
3.0 KiB
Go
118 lines
3.0 KiB
Go
package leetcode
|
||
|
||
// 解法一 Manacher's algorithm,时间复杂度 O(n),空间复杂度 O(n)
|
||
func longestPalindrome(s string) string {
|
||
if len(s) < 2 {
|
||
return s
|
||
}
|
||
newS := make([]rune, 0)
|
||
newS = append(newS, '#')
|
||
for _, c := range s {
|
||
newS = append(newS, c)
|
||
newS = append(newS, '#')
|
||
}
|
||
// dp[i]: 以预处理字符串下标 i 为中心的回文半径(奇数长度时不包括中心)
|
||
// maxRight: 通过中心扩散的方式能够扩散的最右边的下标
|
||
// center: 与 maxRight 对应的中心字符的下标
|
||
// maxLen: 记录最长回文串的半径
|
||
// begin: 记录最长回文串在起始串 s 中的起始下标
|
||
dp, maxRight, center, maxLen, begin := make([]int, len(newS)), 0, 0, 1, 0
|
||
for i := 0; i < len(newS); i++ {
|
||
if i < maxRight {
|
||
// 这一行代码是 Manacher 算法的关键所在
|
||
dp[i] = min(maxRight-i, dp[2*center-i])
|
||
}
|
||
// 中心扩散法更新 dp[i]
|
||
left, right := i-(1+dp[i]), i+(1+dp[i])
|
||
for left >= 0 && right < len(newS) && newS[left] == newS[right] {
|
||
dp[i]++
|
||
left--
|
||
right++
|
||
}
|
||
// 更新 maxRight,它是遍历过的 i 的 i + dp[i] 的最大者
|
||
if i+dp[i] > maxRight {
|
||
maxRight = i + dp[i]
|
||
center = i
|
||
}
|
||
// 记录最长回文子串的长度和相应它在原始字符串中的起点
|
||
if dp[i] > maxLen {
|
||
maxLen = dp[i]
|
||
begin = (i - maxLen) / 2 // 这里要除以 2 因为有我们插入的辅助字符 #
|
||
}
|
||
}
|
||
return s[begin : begin+maxLen]
|
||
}
|
||
|
||
func min(x, y int) int {
|
||
if x < y {
|
||
return x
|
||
}
|
||
return y
|
||
}
|
||
|
||
// 解法二 滑动窗口,时间复杂度 O(n^2),空间复杂度 O(1)
|
||
func longestPalindrome1(s string) string {
|
||
if len(s) == 0 {
|
||
return ""
|
||
}
|
||
left, right, pl, pr := 0, -1, 0, 0
|
||
for left < len(s) {
|
||
// 移动到相同字母的最右边(如果有相同字母)
|
||
for right+1 < len(s) && s[left] == s[right+1] {
|
||
right++
|
||
}
|
||
// 找到回文的边界
|
||
for left-1 >= 0 && right+1 < len(s) && s[left-1] == s[right+1] {
|
||
left--
|
||
right++
|
||
}
|
||
if right-left > pr-pl {
|
||
pl, pr = left, right
|
||
}
|
||
// 重置到下一次寻找回文的中心
|
||
left = (left+right)/2 + 1
|
||
right = left
|
||
}
|
||
return s[pl : pr+1]
|
||
}
|
||
|
||
// 解法三 中心扩散法,时间复杂度 O(n^2),空间复杂度 O(1)
|
||
func longestPalindrome2(s string) string {
|
||
res := ""
|
||
for i := 0; i < len(s); i++ {
|
||
res = maxPalindrome(s, i, i, res)
|
||
res = maxPalindrome(s, i, i+1, res)
|
||
}
|
||
return res
|
||
}
|
||
|
||
func maxPalindrome(s string, i, j int, res string) string {
|
||
sub := ""
|
||
for i >= 0 && j < len(s) && s[i] == s[j] {
|
||
sub = s[i : j+1]
|
||
i--
|
||
j++
|
||
}
|
||
if len(res) < len(sub) {
|
||
return sub
|
||
}
|
||
return res
|
||
}
|
||
|
||
// 解法四 DP,时间复杂度 O(n^2),空间复杂度 O(n^2)
|
||
func longestPalindrome3(s string) string {
|
||
res, dp := "", make([][]bool, len(s))
|
||
for i := 0; i < len(s); i++ {
|
||
dp[i] = make([]bool, len(s))
|
||
}
|
||
for i := len(s) - 1; i >= 0; i-- {
|
||
for j := i; j < len(s); j++ {
|
||
dp[i][j] = (s[i] == s[j]) && ((j-i < 3) || dp[i+1][j-1])
|
||
if dp[i][j] && (res == "" || j-i+1 > len(res)) {
|
||
res = s[i : j+1]
|
||
}
|
||
}
|
||
}
|
||
return res
|
||
}
|