原文链接: https://leetcode-cn.com/problems/M99OJA

中文题目

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

回文串 是正着读和反着读都一样的字符串。

 

示例 1：

输入：s = "google"
输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

示例 2：

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

示例 3：

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

 

提示：

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

 

注意：本题与主站 131 题相同： https://leetcode-cn.com/problems/palindrome-partitioning/

通过代码

高赞题解

本题需要一点前置知识，那就是给定下标[i, j] (i <= j)需要在O(1)时间复杂度内判断该范围内的子串是否是回文。如果不知道怎么做，请先尝试解决647. 回文子串。

如果清楚了以上问题，我们就可以使用动态规划预处理字符串，得到一张映射表，然后用回溯算法就可以解决该问题了（其实就是不断枚举不相交的区间）。

class Solution {
    public String[][] partition(String s) {
        int n = s.length();
        char[] arr = s.toCharArray();
        // 预处理
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = true;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = (arr[i] == arr[j] && dp[i + 1][j - 1]);
            }
        }
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(res, path, s, n, dp, 0);
        // List<List<String>> 转 String[][]，这里不重要
        String[][] ans = new String[res.size()][];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = new String[res.get(i).size()];
            for (int j = 0; j < ans[i].length; j++) {
                ans[i][j] = res.get(i).get(j);
            }
        }
        return ans;
    }

    public void dfs(List<List<String>> res, List<String> path, String s, int n, boolean[][] dp, int pos) {
        if (pos == n) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = pos; i < n; i++) {
            // s[pos:i] （闭区间）是一个回文，所以递归搜索s[i+1, s.length()-1] 
            if (dp[pos][i]) {
                path.add(s.substring(pos, i + 1));
                dfs(res, path, s, n, dp, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }
}

统计信息

通过次数	提交次数	AC比率
3264	4344	75.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言