题目描述

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

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

样例

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

算法分析

• 1、先预处理g[][]数组，g[j][i]表示字符串[j,i]的子字符串是一个回文串
• 2、递归搜索回文串，u代表下一个回文串的起始位置，枚举下一个回文串的最终位置i，若[u,i]组成的字符串是一个回文串，则记录[u,i]组成的回文串，并递归到下一层i + 1的位置
• 3、当u == s.length()时，表示已经分割完整个字符串，将当前记录过的回文串链表加入到ans中
• 4、递归完后需要恢复现场

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

Java 代码

class Solution {
    static List<List<String>> ans = new ArrayList<List<String>>();
    static List<String> path = new ArrayList<String>();
    static boolean[][] g;
    static void init(String s)
    {
        int n = s.length();
        for(int i = 0;i < n;i ++)
            for(int j = 0;j <= i;j ++)
            {
                if(i == j) g[j][i] = true;
                else if(s.charAt(i) == s.charAt(j) && (j + 1 > i - 1 || g[j + 1][i - 1]))
                    g[j][i] = true;
            }
    }
    static void dfs(int u,String s)
    {
        if(u == s.length())
        {
            ans.add(new ArrayList<>(path));
            return ;
        }

        for(int i = u;i < s.length();i ++)
        {
            if(g[u][i])
            {
                path.add(s.substring(u,i + 1));
                dfs(i + 1, s);
                path.remove(path.size() - 1);
            }
        }
    }
    public List<List<String>> partition(String s) {
        ans.clear();
        int n = s.length();
        g = new boolean[n][n];
        init(s);
        dfs(0, s);
        return ans;
    }
}