最长回文子串问题：Go语言实现及复杂度分析

最长回文子串问题：Go语言实现及复杂度分析

最长回文子串问题是要求找到一个字符串中最长的回文子串。以下是几种常见解法的思路和复杂度分析：

1. 暴力解法

思路：

• 检查所有可能的子串，判断是否为回文
• 记录最长的回文子串

Go实现：

func longestPalindrome(s string) string {n := len(s)if n < 2 {return s}maxLen := 1begin := 0for i := 0; i < n-1; i++ {for j := i+1; j < n; j++ {if j-i+1 > maxLen && isPalindrome(s, i, j) {maxLen = j - i + 1begin = i}}}return s[begin : begin+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(n²)，每个子串检查回文O(n)
• 空间复杂度：O(1) - 只使用了常数空间

2. 中心扩展法

思路：

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

Go实现：

func longestPalindrome(s string) string {if len(s) < 2 {return s}start, end := 0, 0for i := 0; i < len(s); i++ {len1 := expandAroundCenter(s, i, i)    // 奇数长度len2 := expandAroundCenter(s, i, i+1)  // 偶数长度maxLen := max(len1, len2)if maxLen > end - start {start = i - (maxLen-1)/2end = i + maxLen/2}}return s[start:end+1]
}func expandAroundCenter(s string, left, right int) int {for left >= 0 && right < len(s) && s[left] == s[right] {left--right++}return right - left - 1
}func max(a, b int) int {if a > b {return a}return b
}

复杂度分析：

• 时间复杂度：O(n²) - 遍历每个中心点O(n)，每个中心扩展O(n)
• 空间复杂度：O(1) - 只使用了常数空间

3. 动态规划

思路：

• 定义dp[i][j]表示s[i…j]是否为回文
• 状态转移方程：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
• 边界条件：单个字符是回文，两个相同字符也是回文

Go实现：

func longestPalindrome(s string) string {n := len(s)if n < 2 {return s}dp := make([][]bool, n)for i := range dp {dp[i] = make([]bool, n)dp[i][i] = true}maxLen := 1begin := 0for j := 1; j < n; j++ {for i := 0; i < j; i++ {if s[i] != s[j] {dp[i][j] = false} else {if j - i < 3 {dp[i][j] = true} else {dp[i][j] = dp[i+1][j-1]}}if dp[i][j] && j-i+1 > maxLen {maxLen = j - i + 1begin = i}}}return s[begin : begin+maxLen]
}

复杂度分析：

• 时间复杂度：O(n²) - 填充n×n的DP表
• 空间复杂度：O(n²) - 需要存储DP表

4. Manacher算法

思路：

• 预处理字符串，插入特殊字符处理偶数长度回文
• 维护一个回文半径数组和当前最远右边界
• 利用对称性减少不必要的计算

Go实现：

func longestPalindrome(s string) string {if len(s) < 2 {return s}// 预处理字符串t := "^#" + strings.Join(strings.Split(s, ""), "#") + "#$"n := len(t)p := make([]int, n)center, right := 0, 0for i := 1; i < n-1; i++ {if right > i {p[i] = min(right-i, p[2*center-i])}// 中心扩展for t[i+p[i]+1] == t[i-p[i]-1] {p[i]++}// 更新最右边界if i+p[i] > right {center, right = i, i+p[i]}}// 找出最大回文子串maxLen, centerIndex := 0, 0for i := 1; i < n-1; i++ {if p[i] > maxLen {maxLen = p[i]centerIndex = i}}start := (centerIndex - maxLen) / 2return s[start : start+maxLen]
}func min(a, b int) int {if a < b {return a}return b
}

复杂度分析：

• 时间复杂度：O(n) - 每个字符最多被处理两次
• 空间复杂度：O(n) - 需要存储预处理字符串和回文半径数组

总结

在实际应用中，中心扩展法通常是较好的选择，因为它实现简单且效率较高。Manacher算法虽然理论复杂度最优，但实现较为复杂，通常只在特别需要优化性能时使用。