131. 分割回文串

题目链接：131. 分割回文串

题目描述

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

核心思考：回溯法（基于切割点的搜索）

本题的目标是找出所有可能的分割方案，这种枚举所有可能组合的问题非常适合使用回溯法。

1. 组合建模：我们可以将分割过程想象成在字符串的 $n-1$ 个间隙中，决定哪些间隙需要“切一刀”。
2. 递归决策：
   • 设当前所在位置为 i，之前最后一次切割的位置为 start。
   • 在位置 i，我们面临两个决策：
     • 不切：继续向后探测 dfs(i + 1, start)。
     • 切一刀（如果合法）：检查当前子串 s[start:i+1] 是否是回文。如果是，则将其加入 path，然后递归进入下一阶段 dfs(i + 1, i + 1)，完成后进行回溯 path.pop()。
3. 终止条件：当遍历索引 i 到达字符串末尾 n 时，如果所有已切开的部分都是回文，将其存入结果集。
4. 性能细节：代码中使用了 Python 的切片反转 temp == temp[::-1] 来快速判断回文。

这种方法通过深度优先搜索，系统地探索了每一个切割点的所有可能性。

解题思路 (Python)

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        path = []

        def dfs(i, start):
            # 终止条件：到达字符串末尾
            if i == n:
                ans.append(path[:])
                return
            
            # 决策 1：不在此处切割工作，继续向后扫描
            # 注意边界：为了保证最后一段能被处理，只有在非最后一位时才可跳过
            if i < n - 1:
                dfs(i + 1, start)

            # 决策 2：在此处尝试切割
            temp = s[start:i + 1]
            if temp == temp[::-1]:
                path.append(temp)
                # 切割后，新的子串起点从 i+1 开始
                dfs(i + 1, i + 1)
                # 回溯
                path.pop()
        
        dfs(0, 0)
        return ans

复杂度分析

• 时间复杂度：$O(N \cdot 2^N)$，其中 $N$ 是字符串的长度。字符串共有 $2^{N-1}$ 种潜在的分割方式，且每一层处理涉及回文检查和列表拷贝。
• 空间复杂度：$O(N)$。递归栈深度及路径数组 path 的规模均由字符串长度决定。