131. 分割回文串 - Palindrome Partitioning

🎯 问题描述（来源于LeetCode）

描述：
给定一个字符串 s，将 s 分割成若干子串，使得每个子串都是回文串。
返回所有可能的分割方案。

说明：

  • 子串是原字符串中连续的一段。
  • 回文串是正读反读相同的字符串。

示例：

  • 示例 1：
1
2
输入: s = "aab"
输出: [["a","a","b"],["aa","b"]]
  • 示例 2：
1
2
输入: s = "a"
输出: [["a"]]

💻 解题思路

思路：回溯法（DFS）扩展子串 + 回文判断

算法步骤

  1. 获取字符串长度 n，初始化结果列表 ans 和当前路径列表 path。
  2. 定义递归函数 dfs(i, left)，其中 i 表示当前扫描到的右边界，left 表示当前子串的起始位置：
    • 如果 i == n，说明所有字符已被分割完毕（此时 left == n），将 path 的副本加入 ans 并返回。
    • 如果 i < n-1，先尝试不切割：递归 dfs(i+1, left)，即继续扩展当前子串。
    • 取出子串 ch = s[left:i+1]，如果 ch 是回文串，则切割：将 ch 加入 path，递归 dfs(i+1, i+1) 开始新的子串，然后回溯弹出。
  3. 从 dfs(0, 0) 开始搜索。
  4. 返回 ans。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        path = []
        n = len(s)
        
        def dfs(i, left):
            if i == n:
                ans.append(path[:])
                return
            if i < n-1:
                dfs(i+1, left)
            ch = s[left:i+1]
            if ch == ch[::-1]:
                path.append(ch)
                dfs(i+1, i+1)
                path.pop()
        
        dfs(0, 0)
        return ans

📊 性能分析

  • 时间复杂度：最坏 O(n⋅2n)O(n \cdot 2^n)，每个字符可能选择切或不切，且每个子串判断回文需要 O(n)O(n)。
  • 空间复杂度：O(n)O(n)，递归栈深度和路径存储。

思考

该解法巧妙地利用两个参数 (i, left) 表示当前正在构建的子串范围 [left, i]，通过“不切割”分支扩展右边界，通过“切割”分支（当子串是回文时）将子串加入路径并开启新子串。
优点：

  • 代码简洁，没有显式的循环枚举切割点，而是通过递归分支隐式枚举所有可能的分割。
  • 当 i == n 时，所有字符必定已被正确处理（因为只有通过切割将 left 推进到 i+1 才能到达 i=n），因此无需额外验证 left == n。
  • 回溯时正确恢复现场，保证路径的独立性。

注意事项：

  • 递归分支顺序（先不切割后切割）保证了子串按顺序枚举，不会遗漏。
  • 对于空字符串 s = ""，函数会直接返回 []（因为 dfs(0,0) 立即到达 i==n，加入空路径，但题目通常不会出现空字符串）。
  • 此解法在 LeetCode 上能够正确通过所有测试用例，是回文分割问题的有效实现。
    如果需要进一步优化，可以预先计算所有子串是否为回文（动态规划），将判断时间降为 O(1)O(1)