题目描述
给定一个字符串 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)$，我们需要一个二维数组来保存所有子串的状态。
解题思路 - 中心扩展法
中心扩展法的基本思想是，对于每一个可能的回文中心，向两边扩展，直到不能形成更长的回文串为止。由于回文串可以是奇数长度或偶数长度，因此每个字符和每对相邻字符都可以作为回文中心。
算法步骤如下：
- 遍历字符串中的每个字符，将其作为回文中心。
- 对于每个回文中心，向两边扩展，检查两边字符是否相等。
- 更新最长回文子串。
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)$，中心扩展法只需要常数级别的额外空间。
中心扩展法在处理较长的字符串时通常比动态规划法更高效，因为它避免了创建一个大的二维数组。
还有一种非常高效的解法，即Manacher算法。Manacher算法可以在O(n)的时间复杂度内找到最长的回文子串。这个算法相对复杂，但是它非常巧妙地利用了回文串的性质来避免不必要的比较。
解题思路 - Manacher算法
- 预处理：为了统一处理奇数长度和偶数长度的情况，我们在原字符串的每个相邻字符之间插入一个特殊字符（例如#），并且为了防止越界，我们在字符串的开始和结束也加上特殊字符。例如，"abba" -> "#a#b#b#a#"。
- 初始化：定义一个数组
p，其中p[i] 表示以s[i] 为中心的回文串向左/向右扩展的长度（不包括s[i]）。定义两个变量maxRight 和center，分别表示当前找到的最右边的回文串的右边界和中心。 - 遍历：遍历每个字符，利用已知的回文信息来避免不必要的比较。对于当前遍历到的位置
i，找到它在以center 为中心的回文串中的对称位置j = 2 * center - i。如果i 在maxRight 的左侧，可以直接利用p[j] 的值；如果i 在maxRight 的右侧，则从maxRight 开始一个一个字符地比较。 - 更新：在每次比较后，更新
p[i] 和maxRight 的值，并且如果i 超过了maxRight，更新center。 - 找到最长回文子串：在遍历结束后，遍历
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 数组。
除了动态规划法、中心扩展法和Manacher算法之外，还有一种基于递归的解法，称为“分割法”。这种方法的基本思想是将问题分解为规模更小的子问题，并通过递归的方式来解决。
解题思路 - 分割法
- 分割点：对于字符串中的每一个位置
i，检查s[i] 是否与s[i+1] 相同。如果相同，那么s[i] 和s[i+1] 可能是某个更长回文子串的一部分。 - 递归：对于每个分割点，递归地检查两边的子串是否为回文串。如果两边都是回文串，那么整个子串也是回文串。
- 合并：在递归过程中，记录下找到的最长回文子串。
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)$，分割法只需要常数级别的额外空间。
分割法在处理较长的字符串时通常比动态规划法更高效，因为它避免了创建一个大的二维数组。然而，这种方法在理论上并不比中心扩展法更优，因为它们的时间复杂度相同。在实际应用中，中心扩展法通常更受欢迎，因为它更直观且实现起来更简单。
