LeetCode LCR 086. 分割回文串

约 6 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
哈希表 深度优先搜索 广度优先搜索 LCR 图

题目描述

✅ LCR 086. 分割回文串

image-20260929010033453

题意分析

把整个字符串按原顺序切成若干非空子串，要求每段都是回文，返回所有切分方案。每个字符必须恰好属于一段，不能跳过或重复使用；本篇 Java 接口返回 String[][]。

可以从左到右枚举每一段的结尾。不同切分前缀可能反复检查同一个区间是否回文，而这个判断只取决于区间本身，因此先预处理回文表，再用回溯枚举合法切分。

解法：回文表预处理与切分回溯

核心思路

[!blue]

f[i][j] 表示闭区间 s[i..j] 是否为回文。长度至少为二时，首尾字符必须相同，内部也必须回文，所以有 f[i][j] = (s[i] == s[j]) && f[i+1][j-1]。

代码将整张表初始化为 true：对角线对应单字符，确实是回文；长度为二时，内部项落在下三角的 f[i+1][i]，将它视为空区间回文，就只需比较两端。其余有效区间都会重新计算，不会误用初值。按 i 从后向前填表，可以保证需要的下一行已经完成。

dfs(i) 中，t 已经记录覆盖 s[0..i-1] 的若干回文段，下一段必须从 i 开始。枚举段尾 j，只有 f[i][j] 为真时才加入 s[i..j]，然后递归到 j+1。起点严格前进，既不会重用字符，也保证搜索终止。

到达 i == n 时，所有字符已被合法段完整覆盖，复制当前路径作为一个答案。每种合法切分的第一段都在当前枚举范围内，余下部分也会递归枚举，因此不会遗漏；不同段尾序列对应不同切分，不需要额外去重。

子调用返回后移除最后一段，恢复当前前缀再尝试其他段尾。保存答案时必须复制路径容器，Java 转成新字符串数组，Go 复制切片内容；字符串本身不可变，可以共享。

解题步骤

  1. 创建全为 true 的回文表，保留单字符和空内区间的基准。
  2. 左端点倒序、右端点从 i+1 开始，按首尾字符和内部区间填表。
  3. 从 dfs(0) 开始，每层枚举当前段尾，只选择表中判定为回文的区间。
  4. 递归到下一段起点 j+1，完成整串时保存路径副本，返回后撤销最后一段。

代码实现

class Solution {
    private int n;
    private String s;
    private boolean[][] f;
    private List<String> t = new ArrayList<>();
    private List<String[]> answer = new ArrayList<>();

    public String[][] partition(String s) {
        n = s.length();
        f = new boolean[n][n];

        // 全部初始化为 true：同时给出「单字符回文」与「空区间回文」两个基准。
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], true);
        }

        // i 倒序：f[i][j] 依赖行号更大的 f[i + 1][j - 1]。
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = s.charAt(i) == s.charAt(j) && f[i + 1][j - 1];
            }
        }

        this.s = s;
        dfs(0);

        return answer.toArray(new String[0][]);
    }

    // i：当前待切分段的起点，s[0..i-1] 已切好并记录在 t 中。
    private void dfs(int i) {
        if (i == s.length()) {
            answer.add(t.toArray(new String[0]));

            return;
        }

        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                t.add(s.substring(i, j + 1));
                // 下一段从 j + 1 开始，写成 j 会让字符被重复使用。
                dfs(j + 1);
                t.remove(t.size() - 1);
            }
        }
    }
}

func partition(s string) (answer [][]string) {
    n := len(s)
    f := make([][]bool, n)
    // 全部初始化为 true：同时给出「单字符回文」与「空区间回文」两个基准。
    for i := range f {
        f[i] = make([]bool, n)
        for j := range f[i] {
            f[i][j] = true
        }
    }
    // i 倒序：f[i][j] 依赖行号更大的 f[i+1][j-1]。
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            f[i][j] = s[i] == s[j] && f[i+1][j-1]
        }
    }

    t := []string{}
    // i：当前待切分段的起点，s[0..i-1] 已切好并记录在 t 中。
    var dfs func(int)
    dfs = func(i int) {
        if i == n {
            answer = append(answer, append([]string(nil), t...))
            return
        }
        for j := i; j < n; j++ {
            if f[i][j] {
                t = append(t, s[i:j+1])
                // 下一段从 j+1 开始，写成 j 会让字符被重复使用。
                dfs(j + 1)
                t = t[:len(t)-1]
            }
        }
    }
    dfs(0)
    return
}

复杂度分析

  • 时间复杂度：$O(n^2+n2^n)$。预处理为 $O(n^2)$；字符串的每个间隙可切或不切，完整划分最多为 $2^{n-1}$ 种，搜索、构造子串及复制输出的最坏总量为 $O(n2^n)$。
  • 空间复杂度：不计输出为 $O(n^2)$，由回文表主导；递归深度、路径段数和当前路径的总字符数都不超过 $n$。输出本身最坏需要 $O(n2^n)$ 空间。

关键点总结

[!green]

  • 回文表只处理与路径无关的区间判定；回溯负责把这些区间拼成覆盖整串的方案。
  • 表的初始化给出单字符和空内部区间的基准，填表顺序保证递推依赖已经计算好。
  • 下一段必须从 j+1 开始，每段非空且相邻无缝，终点 n 表示整串恰好用完。
  • 单字符总能作为一段，因此非空输入至少存在逐字符切分这一种合法方案。

易错点总结

[!yellow]

  • Java 判题接口返回 String[][]，不能直接使用主站 131 的列表返回类型。
  • 回文表必须先处理依赖的短区间，当前左端点倒序；单字符和空内区间要作为回文基准。
  • 切分后下一段从 j+1 开始，保存路径副本并在回溯时撤销。

相似题目

题目 难度 关联与区别
132. 分割回文串 II 困难 回文区间判定相同，原题求最少切割次数，本题输出所有合法划分。
647. 回文子串 中等 同样预处理或枚举回文子串，本题把这些区间作为划分搜索中的可选边。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/15789904
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！