难度: Hard
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab" 输出：1 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a" 输出：0
示例 3：
输入：s = "ab" 输出：1
提示：
1 <= s.length <= 2000s仅由小写英文字母组成
Submission
运行时间: 40 ms
内存: 0.0 MB
class Solution:
def minCut(self, s: str) -> int:
if s == s[::-1]:
return 0
for i in range(len(s)):
if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
return 1
dp = [-1] + [i for i in range(len(s))]
for i in range(2 * len(s) - 1):
l = i // 2
r = i - l
while r < len(s) and l > -1 and s[l] == s[r]:
dp[r + 1] = min(dp[r + 1], dp[l] + 1)
r += 1
l -= 1
return dp[-1]
Explain
这个题解使用了动态规划的思路。首先判断整个字符串是否为回文串，如果是则直接返回0。然后判断是否存在一个分割点，使得分割成的两个子串都是回文串，如果存在则返回1。否则使用动态规划，定义 dp[i] 表示前i个字符组成的子串 s[0:i] 的最小分割次数。状态转移方程为：如果 s[l:r] 是回文串，那么 dp[r] = min(dp[r], dp[l]+1)，其中 l 为 s[0:r] 的任意分割点。最后返回 dp[-1] 即为最小分割次数。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def minCut(self, s: str) -> int:
if s == s[::-1]: # 如果整个字符串是回文串，直接返回0
return 0
for i in range(len(s)): # 判断是否存在一个分割点，分割成两个回文子串
if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
return 1
dp = [-1] + [i for i in range(len(s))] # 初始化dp数组
for i in range(2 * len(s) - 1): # 遍历所有可能的回文中心
l = i // 2
r = i - l
while r < len(s) and l > -1 and s[l] == s[r]: # 如果s[l:r]是回文串
dp[r + 1] = min(dp[r + 1], dp[l] + 1) # 更新dp[r]为 min(dp[r], dp[l]+1)
r += 1
l -= 1
return dp[-1] # 返回最小分割次数 dp[-1]
Explore
在这个问题中，dp数组的初始化方式 '-1' 加上每个索引i的值实际上是为了设置一个最大的分割次数的初始条件。这样的初始化方式确保了在动态规划的过程中，任何一个可能的分割方案都会被考虑。具体来说，'-1' 是为了让dp[0]开始于0，因为字符串s[0:0]是空串，自然不需要分割。而dp[i]初始化为i-1，表示最坏情况下，从头到第i个字符需要分割i-1次，即每个字符单独作为一个回文子串。这样的设置保证了动态规划的过程中dp数组始终有合理的初始值，便于后续的最小值更新。
状态转移方程的设计基于这样的考虑：如果子串s[l:r+1]是回文串，那么在最优的分割方案中，我们可以考虑在位置l之前的子串s[0:l]的最小分割次数加上一次分割（将s[l:r+1]分割出来）。因此，如果s[l:r+1]是回文，dp[r+1]（表示到达r+1位置的最小分割数）可以通过dp[l]（表示到达l位置的最小分割数）加上一次额外的分割得到。我们使用min函数来确保每次都取得可能的最小值，这样可以确保dp[r+1]存储的是到当前位置为止的最小分割次数。
中心扩展法是一种有效检查回文子串的方法。在这个方法中，我们选择一个中心点（或中心对），然后同时向两边扩展l和r，检查扩展后的子串是否仍然保持回文性质。这种方法可以确保遍历所有可能的回文子串，因为它从每一个可能的中心开始，向两边尽可能扩展。在动态规划的过程中，这种检查方式允许我们在发现回文子串时立即使用这个信息来更新dp数组，从而高效地更新最小分割次数。
在代码中实现中心扩展的逻辑涉及选择一个中心点，并从这个中心点开始向两边扩展。具体实现时，如果中心是单个字符（对于奇数长度的回文），中心索引为i/2；如果中心是两个字符（对于偶数长度的回文），则中心索引为i/2和i/2+1。扩展开始前，初始化l（左索引）和r（右索引）为中心位置或中心对。在每次循环中，检查s[l]和s[r]是否相等，如果相等则继续扩展至l-1和r+1。这种方法确保我们从每个可能的中心出发，检测所有可能形成的回文子串。通过这种方式，我们可以在遍历过程中动态更新dp数组，即在发现一个新的回文子串时，使用它来可能地减少之前的分割次数。这种中心扩展技术是检查回文串在算法中的直接应用，有效地结合了理论与实践。