What is the main dynamic programming pattern in Palindrome Partitioning II?

The pattern is state transition dp where dp[i] represents minimum cuts for s[0..i] and updates depend on precomputed palindrome substrings.

Can I optimize space usage for this problem?

Yes, you can reduce the 2D palindrome table to a 1D array for checking palindromes on the fly, though it may complicate updates.

What is the time complexity for large strings?

Filling the palindrome table is O(n^2), and computing dp is also O(n^2), so overall complexity remains quadratic for worst-case inputs.

Why can't a greedy approach work here?

Greedy cuts fail because local palindrome decisions may prevent a globally minimal cut solution, requiring full dp state tracking.

Are single-character substrings always considered palindromes?

Yes, any single character is a palindrome, which simplifies base cases in the dp array and precomputed table.

#132

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

分割回文串 II

给你一个字符串 s ，请你将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数。示例 1：输入： s = "aab" 输出： 1 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。示例 2：输入： s = "a" 输出： 0 示例 …

字符串动态规划

题目描述

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

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

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

lightbulb

解题思路

方法一：动态规划

我们先预处理得到字符串 $s$ 的每一个子串 $s[i..j]$ 是否为回文串，记录在二维数组 $g[i][j]$ 中，其中 $g[i][j]$ 表示子串 $s[i..j]$ 是否为回文串。

接下来，我们定义 $f[i]$ 表示字符串 $s[0..i-1]$ 的最少分割次数，初始时 $f[i]=i$ 。

接下来，我们考虑 $f[i]$ 如何进行状态转移。我们可以枚举上一个分割点 $j$ ，如果子串 $s[j..i]$ 是一个回文串，那么 $f[i]$ 就可以从 $f[j]$ 转移而来。如果 $j=0$ ，那么说明 $s[0..i]$ 本身就是一个回文串，此时不需要进行分割，即 $f[i]=0$ 。因此，状态转移方程如下：

f[i]=\min_{0\leq j \leq i}\begin{cases} f[j-1]+1, & \textit{if}\ g[j][i]=\textit{True} \\ 0, & \textit{if}\ g[0][i]=\textit{True} \end{cases}

答案即为 $f[n]$ ，其中 $n$ 是字符串 $s$ 的长度。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        g = [[True] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                g[i][j] = s[i] == s[j] and g[i + 1][j - 1]
        f = list(range(n))
        for i in range(1, n):
            for j in range(i + 1):
                if g[j][i]:
                    f[i] = min(f[i], 1 + f[j - 1] if j else 0)
        return f[-1]

speed

复杂度分析

指标	值
时间	complexity is O(n^2) due to filling the palindrome table and updating dp for each substring. Space complexity is O(n^2) for the table and O(n) for dp, optimizing lookups for state transitions in dynamic programming.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They may ask if you can precompute palindrome substrings to speed up checks.
question_mark
Expect questions about how to handle overlapping subproblems efficiently.
question_mark
They often probe understanding of the dp state definition and transitions.

warning

常见陷阱

外企场景

error
Failing to precompute palindromic substrings leads to TLE for longer inputs.
error
Incorrect dp initialization can cause off-by-one errors in cut counts.
error
Assuming single-pass greedy partitioning works ignores overlapping subproblems.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return all possible palindrome partitions instead of the minimum cuts.
arrow_right_alt
Handle strings with uppercase letters or special characters in palindrome checks.
arrow_right_alt
Compute minimum cuts for palindromic substrings of a fixed maximum length.

help

常见问题

外企场景

继续练习

#131 分割回文串 #139 单词拆分 #140 单词拆分 II