千问 LeetCode 2472.不重叠回文子字符串的最大数目 Go实现
好的，这是 LeetCode 2472 "不重叠回文子字符串的最大数目" 的 Go 语言实现。
解题思路
核心是动态规划 + 中心扩展法：
1. 定义 dp[i] 表示 s[0..i-1] 中能选出的最大回文子串数目
2. 对于每个位置 i，有两种选择：
- 不选 s[i-1]：dp[i] = dp[i-1]
- 选以某个位置结尾的回文串：找到所有以 i-1 结尾且长度 ≥ k 的回文串
Go 实现
func maxPalindromes(s string, k int) int {
n := len(s)
dp := make([]int, n+1)
// 中心扩展法
for center := 0; center < 2*n-1; center++ {
left := center / 2
right := left + center%2
// 不选当前字符的情况
if left+1 <= n {
dp[left+1] = max(dp[left+1], dp[left])
}
// 向两边扩展，寻找回文串
for left >= 0 && right < n && s[left] == s[right] {
length := right - left + 1
if length >= k {
// 找到长度 ≥ k 的回文串，更新 dp
dp[right+1] = max(dp[right+1], dp[left]+1)
break // 贪心：找到第一个长度 ≥ k 的就停止
}
left--
right++
}
}
return dp[n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
另一种实现（预处理回文串 + DP）
func maxPalindromes(s string, k int) int {
n := len(s)
dp := make([]int, n+1)
// 预处理所有回文串
isPalindrome := make([][]bool, n)
for i := range isPalindrome {
isPalindrome[i] = make([]bool, n)
}
// 从下往上，从左往右填充
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if s[i] == s[j] {
if j-i <= 2 {
isPalindrome[i][j] = true
} else {
isPalindrome[i][j] = isPalindrome[i+1][j-1]
}
}
}
}
// DP
for i := 1; i <= n; i++ {
dp[i] = dp[i-1] // 不选 s[i-1]
// 枚举以 i-1 结尾的回文串
for j := i - k; j >= 0; j-- {
if isPalindrome[j][i-1] {
dp[i] = max(dp[i], dp[j]+1)
break // 贪心优化
}
}
}
return dp[n]
}
优化版本（只检查长度 k 和 k+1）
利用性质：只需检查长度为 k 和 k+1 的回文串，因为更长的回文串可以去掉首尾得到更短的。
func maxPalindromes(s string, k int) int {
n := len(s)
dp := make([]int, n+1)
// 预处理回文串
isPalindrome := make([][]bool, n)
for i := range isPalindrome {
isPalindrome[i] = make([]bool, n)
}
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if s[i] == s[j] {
if j-i <= 2 {
isPalindrome[i][j] = true
} else {
isPalindrome[i][j] = isPalindrome[i+1][j-1]
}
}
}
}
// DP - 只检查长度 k 和 k+1
for i := 1; i <= n; i++ {
dp[i] = dp[i-1]
// 检查长度为 k 的回文串
if i >= k && isPalindrome[i-k][i-1] {
dp[i] = max(dp[i], dp[i-k]+1)
}
// 检查长度为 k+1 的回文串
if i >= k+1 && isPalindrome[i-k-1][i-1] {
dp[i] = max(dp[i], dp[i-k-1]+1)
}
}
return dp[n]
}
示例验证
示例 1：
s = "abaccdbbd", k = 3
输出：2
解释：选择 "aba" 和 "dbbd"
示例 2：
s = "adbcda", k = 2
输出：0
解释：不存在长度 ≥ 2 的回文串
复杂度分析
- 时间复杂度：O(n²)，中心扩展法或预处理回文串
- 空间复杂度：O(n²)（预处理版本）或 O(n)（中心扩展版本）
测试代码
func main() {
// 测试用例
fmt.Println(maxPalindromes("abaccdbbd", 3)) // 输出: 2
fmt.Println(maxPalindromes("adbcda", 2)) // 输出: 0
fmt.Println(maxPalindromes("aaa", 2)) // 输出: 1
fmt.Println(maxPalindromes("abba", 2)) // 输出: 1
}
推荐使用中心扩展法的实现，空间复杂度更优，且不需要额外的预处理数组。一