Leetcode132：分割回文串 II

题目描述：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

代码思路：

1. 预处理字符串（使用Manacher算法的一部分）：

   • 为了方便处理回文串（尤其是偶数长度的回文串），代码首先构造了一个新的字符串 ss。这个新字符串通过在原字符串 s 的每个字符之间以及开头和结尾插入特殊字符（这里是 #）来构造。
   • 这样做的好处是，无论是奇数长度还是偶数长度的回文串，在新字符串 ss 中都会以一个字符为中心形成对称。

2. 使用Manacher算法计算回文半径：

   • 接下来，代码利用Manacher算法的一个变种来计算新字符串 ss 中每个字符的回文半径，并将结果存储在数组 p 中。
   • p[i] 表示以 ss[i] 为中心的回文串的半径长度（注意，这里不包括中心字符本身）。
   • Manacher算法通过利用已知的回文信息来减少不必要的比较，从而提高效率。

3. 转换回文半径为原始字符串的回文信息：

   • 由于 ss 是通过在 s 的字符间插入 # 构造的，因此原始字符串 s 中的回文串信息可以通过 p 数组中的回文半径来计算。
   • 需要注意的是，ss 中的索引 j 和原始字符串 s 中的索引 i 之间存在对应关系，即 j = 2 * i + 1（因为我们在每个字符之间都插入了一个 #）。
   • 因此，当 ss 中的回文中心 j 的回文半径 p[j] 减去 1 后，它表示的是原始字符串 s 中以某个位置为中心的最长回文串的长度。

4. 动态规划求解最少分割次数：

   • 定义一个动态规划数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符所需的最少分割次数。
   • 初始化 dp[0] = -1（表示空字符串不需要分割）。
   • 然后，对于每个可能的子串 s[i:j]（其中 i 从 1 到 n1，j 从 i 到 n1），检查它是否是一个回文串。
   • 如果 s[i:j] 是回文串，则通过检查新字符串 ss 中对应回文中心 mid 的回文半径 p[mid] 是否覆盖 s[i:j] 来判断。具体来说，如果 p[mid] - 1 >= j - i + 1 成立，则说明 s[i:j] 是一个回文串。
   • 如果 s[i:j] 是回文串，则更新 dp[j] 为 dp[i-1] + 1 和当前 dp[j] 的较小值。这里 dp[i-1] + 1 表示在 i-1 位置之前的子串所需的最少分割次数加上当前这个回文子串的一次分割（实际上不需要真的进行分割，因为 s[i:j] 已经是一个完整的回文串了，但这里是为了保持动态规划的状态转移逻辑）。

5. 返回结果：

   • 最后，dp[-1] 存储了整个字符串 s 所需的最少分割次数（注意，由于 dp 数组的索引是从 0 开始的，而字符串 s 的长度是 n1，所以 dp[-1] 实际上对应的是 dp[n1]，即整个字符串的最少分割次数）。

代码实现：

class Solution:def minCut(self, s: str) -> int:# Manacher模版ss = '#'for c in s:ss += c + '#'c = r = 0n = len(ss)p = [0] * nfor i in range(n):k = min(p[2 * c - i],r - i) if i < r else 1while i - k >= 0 and i + k < n and ss[i - k] == ss[i + k]:k += 1p[i] = kif i + k > r:r = i + kc = i# p[i]为 ss 中回文半径 # p[j] - 1为原始串 s 回文长度# i = j * 2 + 1n1 = len(s)dp = [inf] * (n1 + 1)dp[0] = -1for i in range(1,n1 + 1):for j in range(i,n1 + 1):mid = i + j - 1 # 回文中心# 判断s[i:j]是否是回文if  p[mid] - 1 >= j - i + 1: # 中心的回文串长度覆盖s[i:j]dp[j] = min(dp[j],dp[i - 1] + 1)return dp[-1]