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 }