Files
LeetCode-Go/leetcode/0005.Longest-Palindromic-Substring/5. Longest Palindromic Substring.go
2021-03-04 03:11:42 +08:00

118 lines
3.0 KiB
Go
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

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
}