LeetCode第五题: 最长回文子串

简介: 给定一个字符串 `s`​,找到 `s`​ 中最长的回文子串。你可以假设 `s`​ 的最大长度为 1000。

题目描述

  给定一个字符串 s​,找到 s​ 中最长的回文子串。你可以假设 s​ 的最大长度为 1000。

示例

输入: "babad"
输出: "bab" 或者 "aba"
输入: "cbbd"
输出: "bb"

解题思路 - 动态规划法

  动态规划是解决此类问题的一种常见方法。我们定义一个二维数组 dp[i][j]​,其中 dp[i][j]​ 表示字符串从索引 i​ 到 j​ 的子串是否是回文串。状态转移方程为:

  • 如果 s[i] == s[j]​,并且 j - i < 3​ 或者 dp[i+1][j-1]​ 是回文串,那么 dp[i][j]​ 是回文串。
  • 其他情况下,dp[i][j]​ 不是回文串。

Go语言实现 - 动态规划法

func longestPalindrome(s string) string {
   
   
    n := len(s)
    if n < 2 {
   
   
        return s
    }
    maxLen := 1
    begin := 0
    dp := make([][]bool, n)
    for i := range dp {
   
   
        dp[i] = make([]bool, n)
    }
    for i := 0; i < n; i++ {
   
   
        dp[i][i] = true
    }
    for L := 2; L <= n; L++ {
   
   
        for i := 0; i < n; i++ {
   
   
            j := L + i - 1
            if j >= n {
   
   
                break
            }
            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 + 1
                begin = i
            }
        }
    }
    return s[begin : begin+maxLen]
}

算法分析

  • 时间复杂度: $O(n^2)$,其中 $n$ 是字符串的长度。我们需要遍历字符串的所有子串,并且每个子串的判断需要 $O(1)$ 的时间。
  • 空间复杂度: $O(n^2)$,我们需要一个二维数组来保存所有子串的状态。

  ​image

解题思路 - 中心扩展法

  中心扩展法的基本思想是,对于每一个可能的回文中心,向两边扩展,直到不能形成更长的回文串为止。由于回文串可以是奇数长度或偶数长度,因此每个字符和每对相邻字符都可以作为回文中心。
算法步骤如下:

  1. 遍历字符串中的每个字符,将其作为回文中心。
  2. 对于每个回文中心,向两边扩展,检查两边字符是否相等。
  3. 更新最长回文子串。

Go语言实现 - 中心扩展法

func longestPalindrome(s string) string {
   
   
    if len(s) < 2 {
   
   
        return s
    }
    start, maxLen := 0, 1
    for i := 0; i < len(s); i++ {
   
   
        if len(s)-i <= maxLen/2 {
   
   
            break
        }
        left, right := i, i
        for right < len(s)-1 && s[right] == s[right+1] {
   
   
            right++
        }
        i = right
        for right < len(s)-1 && left > 0 && s[right+1] == s[left-1] {
   
   
            right++
            left--
        }
        if right-left+1 > maxLen {
   
   
            start = left
            maxLen = right - left + 1
        }
    }
    return s[start : start+maxLen]
}

算法分析

  • 时间复杂度: $O(n^2)$,虽然看起来有两层循环,但是由于避免了重复访问已经判断过的子串,实际运行时间会比动态规划法要快。
  • 空间复杂度: $O(1)$,中心扩展法只需要常数级别的额外空间。
    中心扩展法在处理较长的字符串时通常比动态规划法更高效,因为它避免了创建一个大的二维数组。

  ​image

  ‍

  还有一种非常高效的解法,即Manacher算法。Manacher算法可以在O(n)的时间复杂度内找到最长的回文子串。这个算法相对复杂,但是它非常巧妙地利用了回文串的性质来避免不必要的比较。

解题思路 - Manacher算法

  1. 预处理:为了统一处理奇数长度和偶数长度的情况,我们在原字符串的每个相邻字符之间插入一个特殊字符(例如#),并且为了防止越界,我们在字符串的开始和结束也加上特殊字符。例如,"abba" -> "#​a#b#​b#a#​"。
  2. 初始化:定义一个数组 p​,其中 p[i]​ 表示以 s[i]​ 为中心的回文串向左/向右扩展的长度(不包括 s[i]​)。定义两个变量 maxRight​ 和 center​,分别表示当前找到的最右边的回文串的右边界和中心。
  3. 遍历:遍历每个字符,利用已知的回文信息来避免不必要的比较。对于当前遍历到的位置 i​,找到它在以 center​ 为中心的回文串中的对称位置 j = 2 * center - i​。如果 i​ 在 maxRight​ 的左侧,可以直接利用 p[j]​ 的值;如果 i​ 在 maxRight​ 的右侧,则从 maxRight​ 开始一个一个字符地比较。
  4. 更新:在每次比较后,更新 p[i]​ 和 maxRight​ 的值,并且如果 i​ 超过了 maxRight​,更新 center​。
  5. 找到最长回文子串:在遍历结束后,遍历 p​ 数组,找到最大的 p[i]​,然后根据 p[i]​ 计算最长回文子串的起始和结束位置。

Go语言实现 - Manacher算法

func longestPalindrome(s string) string {
   
   
    if len(s) < 2 {
   
   
        return s
    }
    t := "#"
    for i := 0; i < len(s); i++ {
   
   
        t += string(s[i]) + "#"
    }
    p := make([]int, len(t))
    maxRight, center := 0, 0
    maxLen, maxLenCenter := 0, 0
    for i := 0; i < len(t); i++ {
   
   
        if i < maxRight {
   
   
            p[i] = min(p[2*center-i], maxRight-i)
        } else {
   
   
            p[i] = 1
        }
        for i-p[i] >= 0 && i+p[i] < len(t) && t[i-p[i]] == t[i+p[i]] {
   
   
            p[i]++
        }
        if i+p[i] > maxRight {
   
   
            maxRight = i + p[i]
            center = i
        }
        if p[i] > maxLen {
   
   
            maxLen = p[i]
            maxLenCenter = i
        }
    }
    start := (maxLenCenter - maxLen + 1) / 2
    end := start + maxLen - 1
    return s[start:end]
}
func min(a, b int) int {
   
   
    if a < b {
   
   
        return a
    }
    return b
}

算法分析

  • 时间复杂度: $O(n)$,Manacher算法巧妙地利用了回文串的对称性质,使得每个字符最多被扩展一次,从而实现了线性时间复杂度。
  • 空间复杂度: $O(n)$,需要额外的空间来存储预处理后的字符串和 p​ 数组。

  ​image

  除了动态规划法、中心扩展法和Manacher算法之外,还有一种基于递归的解法,称为“分割法”。这种方法的基本思想是将问题分解为规模更小的子问题,并通过递归的方式来解决。

解题思路 - 分割法

  1. 分割点:对于字符串中的每一个位置 i​,检查 s[i]​ 是否与 s[i+1]​ 相同。如果相同,那么 s[i]​ 和 s[i+1]​ 可能是某个更长回文子串的一部分。
  2. 递归:对于每个分割点,递归地检查两边的子串是否为回文串。如果两边都是回文串,那么整个子串也是回文串。
  3. 合并:在递归过程中,记录下找到的最长回文子串。

Go语言实现 - 分割法

func longestPalindrome(s string) string {
   
   
    if len(s) < 2 {
   
   
        return s
    }
    res := ""
    for i := 0; i < len(s); i++ {
   
   
        // 检查奇数长度的回文串
        odd := palindrome(s, i, i)
        if len(odd) > len(res) {
   
   
            res = odd
        }
        // 检查偶数长度的回文串
        even := palindrome(s, i, i+1)
        if len(even) > len(res) {
   
   
            res = even
        }
    }
    return res
}
func palindrome(s string, left, right int) string {
   
   
    for left >= 0 && right < len(s) && s[left] == s[right] {
   
   
        left--
        right++
    }
    // 返回以s[left+1:right]为中心的最长回文子串
    return s[left+1 : right]
}

算法分析

  • 时间复杂度: $O(n^2)$,虽然看起来有两层循环,但是由于避免了重复访问已经判断过的子串,实际运行时间会比动态规划法要快。
  • 空间复杂度: $O(1)$,分割法只需要常数级别的额外空间。
    分割法在处理较长的字符串时通常比动态规划法更高效,因为它避免了创建一个大的二维数组。然而,这种方法在理论上并不比中心扩展法更优,因为它们的时间复杂度相同。在实际应用中,中心扩展法通常更受欢迎,因为它更直观且实现起来更简单。

  ​image

  ‍

  ‍

相关文章
|
7天前
|
算法
LeetCode算法题---最长回文子串、N 字形变换(四)
LeetCode算法题---最长回文子串、N 字形变换(四)
25 0
|
7天前
leetcode代码记录(最长回文子串
leetcode代码记录(最长回文子串
10 2
|
7天前
leetcode-5:最长回文子串
leetcode-5:最长回文子串
24 0
|
7天前
|
算法 Go
golang力扣leetcode 5.最长回文子串
golang力扣leetcode 5.最长回文子串
30 1
|
7天前
|
算法 C#
Leetcode算法系列| 5. 最长回文子串
Leetcode算法系列| 5. 最长回文子串
|
10月前
【LeetCode 训练营 3,5】无重复字符的最长子串+最长回文子串
【LeetCode 训练营 3,5】无重复字符的最长子串+最长回文子串
54 1
|
7天前
|
算法
力扣5、 最长回文子串
力扣5、 最长回文子串
|
7月前
|
存储
力扣刷题-最长回文子串
力扣刷题-最长回文子串
|
8月前
|
算法
LeetCode5-最长回文子串
LeetCode5-最长回文子串
|
9月前
|
算法
LeetCode-5 最长回文子串
LeetCode-5 最长回文子串