回溯中等1 种解法

#131分割回文串

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

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

解题主线

递归层的 start 表示下一段起点，循环枚举当前段的终点。

预处理 palindrome[start][end]，可以把递归中的回文判断从 O(n) 降到 O(1)。

只有当前片段为回文时才继续切分后缀。

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

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

时间复杂度

O(n² + n × 2^n)，预处理 O(n²)，最坏输出规模为指数级

空间复杂度

O(n² + n)，不计输出

131. 分割回文串 · 回文预处理 + 回溯切分

java

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

final class Solution {
    public List<List<String>> partition(String s) {
        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