Go语言实现最长回文子串（小白也能学会的字符串算法详解）

解法一：暴力枚举（适合理解）

最直观的方法是检查所有可能的子串，判断是否为回文，并记录最长的那个。

func isPalindrome(s string) bool {    left, right := 0, len(s)-1    for left < right {        if s[left] != s[right] {            return false        }        left++        right--    }    return true}func longestPalindromeBrute(s string) string {    n := len(s)    if n == 0 {        return ""    }        maxLen := 1    start := 0        for i := 0; i < n; i++ {        for j := i; j < n; j++ {            substr := s[i : j+1]            if isPalindrome(substr) && len(substr) > maxLen {                maxLen = len(substr)                start = i            }        }    }        return s[start : start+maxLen]}  

这种方法时间复杂度为 O(n³)，效率较低，但逻辑清晰，适合初学者理解。

解法二：中心扩展法（推荐）

回文串有“中心对称”的特性。我们可以遍历每个字符（以及每两个字符之间），以它为中心向两边扩展，找到最长回文。

注意：回文长度可能是奇数（如 "aba"）或偶数（如 "abba"），所以要分别处理。

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 longestPalindrome(s string) string {    if len(s) == 0 {        return ""    }        start, end := 0, 0        for i := 0; i < len(s); i++ {        len1 := expandAroundCenter(s, i, i)     // 奇数长度        len2 := expandAroundCenter(s, i, i+1)   // 偶数长度        maxLen := len1        if len2 > maxLen {            maxLen = len2        }                if maxLen > end-start {            start = i - (maxLen-1)/2            end = i + maxLen/2        }    }        return s[start : end+1]}  

该方法时间复杂度为 O(n²)，空间复杂度 O(1)，是面试中最常被接受的解法。

完整测试代码

package mainimport "fmt"// 此处插入上面的 longestPalindrome 函数func main() {    testCases := []string{"babad", "cbbd", "a", "ac", "racecar"}    for _, s := range testCases {        result := longestPalindrome(s)        fmt.Printf("输入: %s → 最长回文子串: %s\n", s, result)    }}  

总结

通过本文，你已经掌握了使用 Go语言 解决 最长回文子串 问题的两种方法。对于初学者，建议先理解暴力法，再掌握更高效的中心扩展法。

这些技巧不仅适用于面试，也体现了 字符串算法 的核心思想——利用问题的对称性或结构特性来优化解法。

继续练习类似问题（如最长公共子串、编辑距离等），你的 回文字符串 和字符串处理能力会越来越强！