131. 分割回文串

LeetCode 131¹ · 中等 · 回溯

题

把字符串切成若干段，要求每一段都是回文，返回所有切法。

例：s = "aab" → [["a","a","b"],["aa","b"]]。

一句话

从位置 start 出发，枚举这一段的结尾 end，s[start..end] 是回文才往下切；判回文用预处理好的 DP 表。

关键技巧

把切割翻译成组合。 长度 \(n\) 的串有 \(n-1\) 个缝，每种切法就是缝的一个子集——于是套「从 start 往后挑」的回溯：本层决定第一段到哪结束，剩下的交给下一层。

回文表预处理。 回溯里会反复问同一个区间是否回文，每次 \(O(n)\) 判太浪费。区间 DP：

\(pal[i][j]\) 依赖 \(pal[i+1][\cdot]\)，所以 i 从大到小填。\(O(n^2)\) 建表后每次查询 \(O(1)\)。

剪枝就在判回文。 不是回文的前缀直接跳过，不展开子树。

解

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        pal = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])

        res, path = [], []

        def dfs(start):
            if start == n:
                res.append(path[:])
                return
            for end in range(start, n):
                if pal[start][end]:
                    path.append(s[start:end + 1])
                    dfs(end + 1)
                    path.pop()

        dfs(0)
        return res

时间 \(O(n \cdot 2^n)\)（最坏全同字符，\(2^{n-1}\) 种切法，每种拷贝 \(O(n)\)），空间 \(O(n^2)\) 回文表。

延伸

• 只要最少切几刀（LeetCode 132）：不要枚举方案，改成一维 DP cut[j] = min(cut[i-1] + 1 for pal[i][j])，\(O(n^2)\)。
• 回文表同款 DP 见 5. 最长回文子串；那题还能用中心扩展把空间降到 \(O(1)\)。
• 「枚举下一段的结尾」这个切法骨架与 139. 单词拆分 相同——那题只问可行性，于是可以 DP 掉。

s = Solution()
norm = lambda xs: sorted(xs)
assert norm(s.partition("aab")) == norm([["a", "a", "b"], ["aa", "b"]])
assert s.partition("a") == [["a"]]
assert norm(s.partition("aaa")) == norm([["a", "a", "a"], ["a", "aa"], ["aa", "a"], ["aaa"]])
assert s.partition("ab") == [["a", "b"]]