题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

样例

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

算法1

(DFS) 时间复杂度：$O(2^n)$

* dp预处理每部分子串是否是回文串，注意数组的赋值顺序应该逐列赋值。
* 此题相当于在字符串中的各个位置放置板子来分割字符串，每个位置都有放与不放两种方式，指数级别时间复杂度。
* 指数级别的题目一般都是DFS暴搜
* 从第0个位置开始搜索，如果当前串是回文串，则从下个位置开始搜索，否则回溯。

Java 代码

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
    boolean[][] f;
    public List<List<String>> partition(String s) {
        int n = s.length();
        f = new boolean[n][n];
        for(int j = 0; j < n; j++){
            for(int i = 0; i <= j; i++){
                if(i == j) f[i][j] = true;
                else{
                    if(s.charAt(i) == s.charAt(j)){
                        if(i + 1 > j - 1 || f[i+1][j-1]){
                            f[i][j] = true;
                        }
                    }
                }
            }
        }

        dfs(s,0);
        return res;
    }

    void dfs(String s, int u){
        if(u == s.length()){
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = u; i < s.length(); i++){
            if(f[u][i]){
                list.add(s.substring(u,i+1));
                dfs(s,i+1);
                list.remove(list.size()-1);
            }
        }
    }
}