【华为机试】5. 最长回文子串

5. 最长回文子串

描述

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2

输入：s = “cbbd”
输出：“bb”

示例 3

输入：s = “a”
输出：“a”

示例 4

输入：s = “ac”
输出：“a”

提示

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

解题思路

方法一：中心扩展法（推荐）

核心思想：

• 以每个字符为中心，向两边扩展寻找回文
• 考虑奇数长度和偶数长度的回文

算法步骤：

1. 遍历字符串的每个位置
2. 以当前位置为中心，向两边扩展
3. 分别处理奇数长度和偶数长度的回文
4. 记录最长回文的起始位置和长度

时间复杂度：O(n²)
空间复杂度：O(1)

方法二：动态规划

核心思想：

• 使用dp[i][j]表示s[i:j+1]是否为回文
• 状态转移：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

算法步骤：

1. 创建二维dp数组
2. 初始化长度为1和2的回文
3. 按长度递增填充dp数组
4. 记录最长回文的位置

时间复杂度：O(n²)
空间复杂度：O(n²)

方法三：Manacher算法

核心思想：

• 使用马拉车算法在线性时间内找到最长回文
• 利用回文的对称性质优化计算

算法步骤：

1. 预处理字符串，插入分隔符
2. 维护回文半径数组
3. 利用对称性质优化扩展
4. 找到最大回文半径

时间复杂度：O(n)
空间复杂度：O(n)

方法四：暴力解法

核心思想：

• 枚举所有可能的子串
• 检查每个子串是否为回文

算法步骤：

1. 双重循环枚举所有子串
2. 检查每个子串是否为回文
3. 记录最长回文

时间复杂度：O(n³)
空间复杂度：O(1)

代码实现

// 方法一：中心扩展法
func longestPalindrome1(s string) string {if len(s) < 2 {return s}start, maxLen := 0, 1for i := 0; i < len(s); i++ {// 奇数长度回文len1 := expandAroundCenter(s, i, i)// 偶数长度回文len2 := expandAroundCenter(s, i, i+1)maxLenCur := max(len1, len2)if maxLenCur > maxLen {start = i - (maxLenCur-1)/2maxLen = maxLenCur}}return s[start : start+maxLen]
}func expandAroundCenter(s string, left, right int) int {for left >= 0 && right < len(s) && s[left] == s[right] {left--right++}return right - left - 1
}

复杂度分析

• 时间复杂度：O(n²)，其中n是字符串长度
• 空间复杂度：O(1)，只使用常数个变量

测试用例

func main() {// 测试用例1s1 := "babad"fmt.Printf("测试用例1: s=%s, 结果=%s\n", s1, longestPalindrome1(s1))// 测试用例2s2 := "cbbd"fmt.Printf("测试用例2: s=%s, 结果=%s\n", s2, longestPalindrome1(s2))// 测试用例3s3 := "a"fmt.Printf("测试用例3: s=%s, 结果=%s\n", s3, longestPalindrome1(s3))
}

完整题解代码

package mainimport "fmt"// 方法一：中心扩展法（推荐）
// 时间复杂度：O(n²)，空间复杂度：O(1)
func longestPalindrome1(s string) string {if len(s) < 2 {return s}start, maxLen := 0, 1for i := 0; i < len(s); i++ {// 奇数长度回文len1 := expandAroundCenter(s, i, i)// 偶数长度回文len2 := expandAroundCenter(s, i, i+1)maxLenCur := max(len1, len2)if maxLenCur > maxLen {start = i - (maxLenCur-1)/2maxLen = maxLenCur}}return s[start : start+maxLen]
}func expandAroundCenter(s string, left, right int) int {for left >= 0 && right < len(s) && s[left] == s[right] {left--right++}return right - left - 1
}// 方法二：动态规划
// 时间复杂度：O(n²)，空间复杂度：O(n²)
func longestPalindrome2(s string) string {if len(s) < 2 {return s}n := len(s)dp := make([][]bool, n)for i := range dp {dp[i] = make([]bool, n)}start, maxLen := 0, 1// 初始化长度为1的回文for i := 0; i < n; i++ {dp[i][i] = true}// 初始化长度为2的回文for i := 0; i < n-1; i++ {if s[i] == s[i+1] {dp[i][i+1] = truestart = imaxLen = 2}}// 按长度递增填充dp数组for length := 3; length <= n; length++ {for i := 0; i <= n-length; i++ {j := i + length - 1if s[i] == s[j] && dp[i+1][j-1] {dp[i][j] = trueif length > maxLen {start = imaxLen = length}}}}return s[start : start+maxLen]
}// 方法三：Manacher算法
// 时间复杂度：O(n)，空间复杂度：O(n)
func longestPalindrome3(s string) string {if len(s) < 2 {return s}// 预处理字符串，插入分隔符t := "#"for _, char := range s {t += string(char) + "#"}n := len(t)p := make([]int, n)center, right := 0, 0// 计算回文半径for i := 0; i < n; i++ {if i < right {mirror := 2*center - ip[i] = min(right-i, p[mirror])}// 尝试扩展left := i - (p[i] + 1)right_bound := i + (p[i] + 1)for left >= 0 && right_bound < n && t[left] == t[right_bound] {p[i]++left--right_bound++}// 更新中心点和右边界if i+p[i] > right {center = iright = i + p[i]}}// 找到最大回文半径maxRadius := 0maxCenter := 0for i := 0; i < n; i++ {if p[i] > maxRadius {maxRadius = p[i]maxCenter = i}}// 转换回原字符串的索引start := (maxCenter - maxRadius) / 2end := (maxCenter + maxRadius) / 2return s[start:end]
}// 方法四：暴力解法
// 时间复杂度：O(n³)，空间复杂度：O(1)
func longestPalindrome4(s string) string {if len(s) < 2 {return s}start, maxLen := 0, 1for i := 0; i < len(s); i++ {for j := i + 1; j < len(s); j++ {if isPalindrome(s, i, j) && j-i+1 > maxLen {start = imaxLen = j - i + 1}}}return s[start : start+maxLen]
}func isPalindrome(s string, left, right int) bool {for left < right {if s[left] != s[right] {return false}left++right--}return true
}// 方法五：优化的中心扩展法
// 时间复杂度：O(n²)，空间复杂度：O(1)
func longestPalindrome5(s string) string {if len(s) < 2 {return s}start, maxLen := 0, 1for i := 0; i < len(s); i++ {// 奇数长度回文len1 := expandAroundCenterOptimized(s, i, i)// 偶数长度回文len2 := expandAroundCenterOptimized(s, i, i+1)maxLenCur := max(len1, len2)if maxLenCur > maxLen {start = i - (maxLenCur-1)/2maxLen = maxLenCur}}return s[start : start+maxLen]
}func expandAroundCenterOptimized(s string, left, right int) int {for left >= 0 && right < len(s) && s[left] == s[right] {left--right++}return right - left - 1
}// 方法六：使用字符串哈希（Rabin-Karp思想）
// 时间复杂度：O(n²)，空间复杂度：O(1)
func longestPalindrome6(s string) string {if len(s) < 2 {return s}start, maxLen := 0, 1for i := 0; i < len(s); i++ {// 奇数长度回文len1 := expandAroundCenter(s, i, i)// 偶数长度回文len2 := expandAroundCenter(s, i, i+1)maxLenCur := max(len1, len2)if maxLenCur > maxLen {start = i - (maxLenCur-1)/2maxLen = maxLenCur}}return s[start : start+maxLen]
}// 辅助函数
func max(a, b int) int {if a > b {return a}return b
}func min(a, b int) int {if a < b {return a}return b
}func main() {fmt.Println("=== 5. 最长回文子串 ===")// 测试用例1s1 := "babad"fmt.Printf("测试用例1: s=%s\n", s1)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s1))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s1))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s1))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s1))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s1))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s1))fmt.Println()// 测试用例2s2 := "cbbd"fmt.Printf("测试用例2: s=%s\n", s2)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s2))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s2))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s2))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s2))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s2))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s2))fmt.Println()// 测试用例3s3 := "a"fmt.Printf("测试用例3: s=%s\n", s3)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s3))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s3))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s3))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s3))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s3))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s3))fmt.Println()// 测试用例4s4 := "ac"fmt.Printf("测试用例4: s=%s\n", s4)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s4))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s4))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s4))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s4))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s4))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s4))fmt.Println()// 额外测试用例s5 := "racecar"fmt.Printf("额外测试: s=%s\n", s5)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s5))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s5))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s5))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s5))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s5))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s5))fmt.Println()// 边界测试用例s6 := ""fmt.Printf("边界测试: s=%s\n", s6)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s6))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s6))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s6))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s6))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s6))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s6))fmt.Println()// 复杂测试用例s7 := "abbaabba"fmt.Printf("复杂测试: s=%s\n", s7)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s7))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s7))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s7))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s7))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s7))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s7))fmt.Println()// 全相同字符测试用例s8 := "aaaa"fmt.Printf("全相同字符测试: s=%s\n", s8)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s8))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s8))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s8))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s8))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s8))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s8))fmt.Println()// 数字字符串测试用例s9 := "12321"fmt.Printf("数字字符串测试: s=%s\n", s9)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s9))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s9))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s9))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s9))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s9))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s9))fmt.Println()// 混合字符串测试用例s10 := "a1b2c3c2b1a"fmt.Printf("混合字符串测试: s=%s\n", s10)fmt.Printf("方法一结果: %s\n", longestPalindrome1(s10))fmt.Printf("方法二结果: %s\n", longestPalindrome2(s10))fmt.Printf("方法三结果: %s\n", longestPalindrome3(s10))fmt.Printf("方法四结果: %s\n", longestPalindrome4(s10))fmt.Printf("方法五结果: %s\n", longestPalindrome5(s10))fmt.Printf("方法六结果: %s\n", longestPalindrome6(s10))
}