LeetCode 131. 分割回文串

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

解释： 有两种可能的分割方式：

1. 分割成 "a"、"a"、"b"（都是回文）。
2. 分割成 "aa"、"b"（"aa" 是回文）。

题目理解

我们需要找到所有可能的方式，将字符串切割成若干段，每一段都是回文串。
比如 "aab"：

• 第一刀可以在第一个字符 'a' 后切，得到 "a" 和剩余 "ab"。然后 "ab" 继续切，但 "ab" 不是回文，所以需要更细的切割，最终得到 ["a","a","b"]。
• 第一刀可以在第二个字符 'a' 后切（即前两个字符 "aa" 作为一段），剩余 "b"，得到 ["aa","b"]。

这本质上是一个 组合搜索 问题：在字符串的每个可能位置决定是否切割，并且要确保每一段都是回文。

核心思路

我们可以用 回溯（DFS） 来搜索所有分割方案：

1. 从字符串的起始位置 start 开始，尝试所有可能的结束位置 end（即从 start 到字符串末尾）。
2. 如果子串 s[start:end+1] 是回文，则选择这一段，然后递归地从 end+1 开始继续分割。
3. 当递归到字符串末尾时，说明找到了一个完整的分割方案，将其加入答案。

关键点：

• 需要快速判断任意子串是否回文，可以预计算一个回文表。
• 回溯时，记录当前路径（已选择的回文子串列表），到达末尾时保存路径。

逐步讲解

步骤 1：预处理回文判断

为了在 O(1) 时间内判断任意子串 s[i:j+1] 是否回文，我们可以用动态规划提前计算一个二维表 isPalindrome[i][j]，表示 s[i..j] 是否是回文。
状态转移方程：

• 如果 s[i] == s[j] 且 (j - i <= 2 或 isPalindrome[i+1][j-1] 为真)，那么 isPalindrome[i][j] = true。
• 否则为 false。

计算顺序：由于 isPalindrome[i][j] 依赖于 i+1, j-1，所以 i 从大到小遍历，j 从 i 到末尾。

步骤 2：回溯搜索设计

我们写一个递归函数 backtrack(start, path)：

• start 表示当前待分割的子串起始索引。
• path 是当前已选择的回文子串列表。
• 如果 start == len(s)，说明已经分割完整个字符串，将 path 的副本加入答案。
• 否则，从 start 到 len(s)-1 枚举结束位置 end：
  • 如果 isPalindrome[start][end] 为真，说明 s[start..end] 是回文。
  • 将 s[start..end] 加入 path。
  • 递归调用 backtrack(end+1, path)。
  • 回溯：从 path 中移除刚才加入的子串。

步骤 3：举例说明

以 s = "aab" 为例：

1. 预处理 isPalindrome：

   • "a" (0,0) 是回文，(1,1) 是回文，(2,2) 是回文。
   • "aa" (0,1)：s[0]==s[1] 且长度 2，是回文。
   • "ab" (1,2)：s[1]!=s[2]，不是回文。
   • "aab" (0,2)：s[0]!=s[2]，不是回文。

2. 回溯过程：

   • 初始 start=0：
     • end=0：子串 "a" 是回文，加入 path = ["a"]，递归 start=1。
       • start=1：
         • end=1：子串 "a" 是回文，path = ["a","a"]，递归 start=2。
           • start=2：
             • end=2：子串 "b" 是回文，path = ["a","a","b"]，递归 start=3（结束），记录方案。
         • end=2：子串 "ab" 不是回文，跳过。
     • end=1：子串 "aa" 是回文，path = ["aa"]，递归 start=2。
       • start=2：
         • end=2：子串 "b" 是回文，path = ["aa","b"]，递归 start=3，记录方案。
     • end=2：子串 "aab" 不是回文，跳过。

最终得到两种方案：[["a","a","b"], ["aa","b"]]。

复杂度分析

• 时间复杂度：O(n * 2^n)，最坏情况下所有子串都是回文（如全相同字符），那么每个分割点都可选或不选，有 2^(n-1) 种方案，每种方案生成需要 O(n) 时间（复制路径）。预处理回文表 O(n²)。
• 空间复杂度：O(n²) 用于存储回文表，O(n) 递归栈和路径存储。

代码实现（Python示例）

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        # 1. 预处理回文表
        is_pal = [[False] * n for _ in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j] and (j - i <= 2 or is_pal[i+1][j-1]):
                    is_pal[i][j] = True
        
        res = []
        path = []
        
        # 2. 回溯函数
        def backtrack(start):
            if start == n:
                res.append(path[:])  # 记录完整分割方案
                return
            for end in range(start, n):
                if is_pal[start][end]:  # 当前子串是回文
                    path.append(s[start:end+1])
                    backtrack(end+1)
                    path.pop()  # 回溯
        
        backtrack(0)
        return res

总结

这道题是一个典型的 回溯搜索 + 预处理优化 的题目：

• 回溯用于枚举所有可能的分割点。
• 预处理回文表避免重复判断，提高效率。
• 关键思想是：每次选择一段回文子串，然后对剩余部分递归分割，直到字符串末尾。

通过这道题，你可以加深对 回溯剪枝 和 子串动态规划预处理 的理解，这在很多字符串分割问题中非常有用。