回溯中等1 种解法

#131分割回文串

把字符串切分为若干回文子串，返回所有可能的切分方案。

#回溯#字符串#动态规划#回文

原题

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

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

查看原题

解题主线

递归层的 start 表示下一段起点，循环枚举当前段的终点。
预处理 palindrome[start][end]，可以把递归中的回文判断从 O(n) 降到 O(1)。
只有当前片段为回文时才继续切分后缀。

解法 1：回文预处理 + 回溯切分

先动态规划出所有回文区间，再回溯枚举终点，只沿回文区间继续搜索。

时间复杂度： O(n² + n × 2^n)，预处理 O(n²)，最坏输出规模为指数级
空间复杂度： O(n² + n)，不计输出

JAVA

import java.util.ArrayList;
import java.util.List;

final class Solution {
    public List<List<String>> partition(String s) {
        // palindrome[start][end] 表示闭区间子串是否为回文。
        // 按 start 递减预处理，确保转移依赖的内层区间已计算。
        // 回溯中的 start 是下一段起点，只沿回文区间扩展。
        // start 到达末尾时，当前路径才是一组完整切分。
        int n = s.length();
        boolean[][] palindrome = new boolean[n][n];
        for (int start = n - 1; start >= 0; start--) {
            for (int end = start; end < n; end++) {
                palindrome[start][end] = s.charAt(start) == s.charAt(end)
                        && (end - start <= 2 || palindrome[start + 1][end - 1]);
            }
        }
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, palindrome, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(String s, int start, boolean[][] palindrome,
                           List<String> path, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (!palindrome[start][end]) {
                continue;
            }
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, palindrome, path, result);
            path.remove(path.size() - 1);
        }
    }
}

边界与易错点

start 到达字符串末尾时，应保存路径并返回。
每次加入的是当前切片 s.substring(start, end + 1)，撤销时只删除最后一段。
若每个搜索分支都重新双指针判断回文，会产生大量重复比较。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q131_partitionPalindrome.java