LC131　分割回文串¶

中等通过率 75.1%python3核心代码模式回溯样例通过牛客 AC字符串动态规划回溯

一句话

枚举第一刀切在哪，切下的前缀是回文才往下递归，切到串尾收一份方案。

解题思路¶

这题考什么¶

分割方案的结构是「切点集合」：在 s 的 n-1 个字符缝里各选切或不切。直接枚举 2 的 (n-1) 次方种切法再逐个验证，n = 16 时是 3.3e4 种，每种验证 O(n)，勉强能跑但全是无效功。

回溯的做法是把「回文」这条约束提到枚举过程里：设 dfs(start) 表示「s 的前 start 个字符已经切好，剩下 s[start:] 待切」，这一层枚举这一段的右端点 end，只有 s[start..end] 是回文时才递归 dfs(end+1)。非回文的前缀连同它下面的整棵子树一起被砍掉，这是本题的全部剪枝。

s = "aab"
dfs(0): "a" 回文 -> dfs(1): "a" 回文 -> dfs(2): "b" 回文 -> dfs(3) 收 [a,a,b]
                           "ab" 不回文，剪
        "aa" 回文 -> dfs(2): "b" 回文 -> dfs(3) 收 [aa,b]
        "aab" 不回文，剪

「s[start..end] 是不是回文」会被反复问到（不同的切法共享同一段子串），所以先用区间动态规划预处理成表：

is_pal[i][j] = (s[i] == s[j]) 且 is_pal[i+1][j-1]

即「两端字符相同且去掉两端后仍是回文」。按 i 从大到小、j 从小到大填，用到 is_pal[i+1][...] 时它已经算好。长度 0 与 1 的区间恒为回文，由初值 True 覆盖。有了这张表，判回文从 O(n) 降成一次查表 O(1)。回文的判定与区间递推见回文，区间动态规划的一般形式见区间 DP；回溯的「选择 -> 递归 -> 撤销」三步见 DFS 深度优先搜索。

数据规模与复杂度¶

1 <= s.length <= 16，仅小写字母。预处理表 O(n 的平方) = 256 格。搜索树的叶子数上界是 2 的 (n-1) 次方 = 3.3e4（全部切法），最坏用例是 16 个相同字母（如 "aaaa...a"），此时每段都是回文，一个分支都剪不掉， 3.3e4 条方案各自要拷贝一份平均长度 8 的列表，约 2.6e5 次基本操作，仍是毫秒级。普通字符串上非回文前缀会砍掉绝大部分子树，实际远小于这个上界。空间 O(n 的平方) 存 is_pal 表，加 O(n) 的 path 与递归栈。

坑在哪¶

is_pal 的填表顺序不能随手写成 i 从小到大。递推式依赖 is_pal[i+1][j-1]，即行号更大的那一行，所以 i 必须倒序遍历；写成正序时它还没被算出来，读到的是初值 True，会把 "ab" 之类判成回文，产出一堆非法分割。
初值必须是 True 而不是 False。当 j == i + 1（长度 2 的区间）时，递推式会访问 is_pal[i+1][i]，这是个空区间，语义上是回文。初值给 False 的话，所有长度为 2 的回文（如 "aa"）都会被判成非回文，示例 1 的 [aa,b] 直接丢失。
切片 s[start:end + 1] 的右端要 +1。Python 切片右开，写成 s[start:end] 会少一个字符，拼出来的方案连不成原串。
递归传的是 end + 1，即下一段从被切走那段的下一个字符开始。传 end 会让同一个字符被两段共用，方案拼起来比原串长。
收答案必须写 path[:] 做一份拷贝。path 是全程复用的同一个列表，直接追加它本身的话，res 里存的全是同一个对象的引用，回溯结束时 path 已被弹空，输出会变成一堆空列表。
出口是 start == n。因为每段至少切走一个字符，start 只增不减，不会跳过 n，用相等判断安全。
本题在 meta.json 的 judge 里配了 unordered：官方也没规定方案之间的先后，哪种分割先输出都对。放宽的只是顶层顺序—— 每种分割内部的子串顺序是有意义的，把它们首尾相接必须还原成原串 s， ["b","a","a"] 与 ["a","a","b"] 不是一回事，这一层绝不放宽。顺序放宽也不等于内容放宽：同一种分割吐两遍照样判错，本题「按切点从左到右推进」保证了每种切法只被枚举一次。

样例复核¶

s = "aab" 的 is_pal 表里，"aa" 与三个单字符为回文，"ab" 与 "aab" 不是。按上图的搜索过程产出 [["a","a","b"],["aa","b"]]，共 2 种，与样例一致。

参考实现¶

solutions/leetcode/LC131/sol.py
from typing import List, Optional


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        # is_pal[i][j] 表示 s[i..j] 是不是回文。初值 True 是为了让长度 0 与 1 的区间
        # 天然成立——递推式在 j == i + 1 时会读到空区间 is_pal[i+1][i]
        is_pal = [[True] * n for _ in range(n)]
        # i 必须倒序：递推依赖 is_pal[i+1][j-1]，正序时那一行还没算出来
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                # 两端字符相同，且去掉两端后仍是回文
                is_pal[i][j] = s[i] == s[j] and is_pal[i + 1][j - 1]

        # res 收方案，path 是当前已经切下来的那几段子串
        res = []
        path = []

        def dfs(start: int) -> None:
            # 切到串尾即凑成一种完整分割；path[:] 是必需的拷贝，path 还要继续被改
            if start == n:
                res.append(path[:])
                return
            # 这一层枚举「这一段切到哪个字符为止」，end 是本段的右端点（闭区间）
            for end in range(start, n):
                # 剪枝：本段不是回文，它下面的整棵子树都不可能产出合法方案
                if not is_pal[start][end]:
                    continue
                # 选：切片右开，所以右端要 +1 才能取到 s[end] 这个字符
                path.append(s[start:end + 1])
                # 递归：下一段从被切走那段的下一个字符开始，传 end 会让字符被两段共用
                dfs(end + 1)
                path.pop()          # 撤销：弹回来，让本段的右端点往后挪一位

        dfs(0)
        return res

LC131 分割回文串¶