算法题：最长回文子串

编码如写诗

发布于 2026-03-02 20:47:12

690

文章被收录于专栏：编码如写诗编码如写诗

算法题：最长回文子串

今天刷到道挺有意思的题，最长回文子串，LeetCode第5题。

题目是这样的：给你一个字符串，找到其中最长的回文子串。

回文就是正读反读都一样的字符串，比如"aba"、"abba"。

题目理解

举个栗子，字符串是"babad"。

最长回文子串是"bab"或"aba"，长度都是3。

如果是"cbbd"，最长回文子串是"bb"，长度是2。

简单来说，就是在一个字符串里找最长的对称子串。

思路分析

最暴力的解法就是枚举所有子串，然后判断是不是回文。

这个思路听着简单，但时间复杂度是O(n³)，太慢了。

稍微聪明点的方法是中心扩散。

以每个字符为中心（或两个字符中间为中心），向两边扩散。

如果是回文就继续扩，不是就停。

记录最长的那个。

这个方法的复杂度是O(n²)。

还有一种方法是用动态规划。

定义dp[i][j]表示s[i:j+1]是不是回文。

状态转移：如果s[i]==s[j]，且dp[i+1][j-1]是回文，那么dp[i][j]就是回文。

这个方法复杂度也是O(n²)，但空间复杂度是O(n²)，比中心扩散费空间。

复杂度分析

中心扩散法：

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

动态规划法：

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

代码实现

package main

import (
"fmt"
)

// 中心扩散法
func longestPalindrome(s string) string {
iflen(s) < 2 {
return s
 }

 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]
}

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 longestPalindromeDP(s string) string {
iflen(s) < 2 {
return s
 }

 n := len(s)
 dp := make([][]bool, n)
for i := range dp {
  dp[i] = make([]bool, n)
 }

 start, maxLen := 0, 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] = true
   start = i
   maxLen = 2
  }
 }

// 检查长度大于2的子串
for length := 3; length <= n; length++ {
for i := 0; i <= n-length; i++ {
   j := i + length - 1
   if s[i] == s[j] && dp[i+1][j-1] {
    dp[i][j] = true
    start = i
    maxLen = length
   }
  }
 }

return s[start : start+maxLen]
}

func main() {
// 测试用例
 s1 := "babad"
 fmt.Printf("输入: %s, 最长回文: %s\n", s1, longestPalindrome(s1))

 s2 := "cbbd"
 fmt.Printf("输入: %s, 最长回文: %s\n", s2, longestPalindrome(s2))

 s3 := "a"
 fmt.Printf("输入: %s, 最长回文: %s\n", s3, longestPalindrome(s3))

 s4 := "ac"
 fmt.Printf("输入: %s, 最长回文: %s\n", s4, longestPalindrome(s4))

// 测试动态规划法
 fmt.Println("\n使用动态规划法:")
 fmt.Printf("输入: %s, 最长回文: %s\n", s1, longestPalindromeDP(s1))
 fmt.Printf("输入: %s, 最长回文: %s\n", s2, longestPalindromeDP(s2))
}