一. 题目

二. 思路

1. 迭代加深

• 隔板是每段的结尾。

• 迭代加深枚举的隔板数量。

• 然后dfs，直到选出所有隔板。

• 中间可以剪枝，当前隔板是否合法。

• 特殊处理：第一块隔板是0开头；最后一块隔板不在字符串末尾，则最后一段是最后隔板位置+1~s.length-1。

• 判断回文：字符串哈希、DP、枚举。

2. 朴素dfs

• 从当前位置枚举合法的终点隔板，直到当前位置越界。

三. 代码

1. 迭代加深

/*
    迭代加深+枚举隔板
    隔板是每个分割字符串的末尾字符
 */
class Solution
{
    static final int N = 20;
    int[] path = new int[N];//隔板
    final List<List<String>> ans = new ArrayList<>();
    final List<String> temp = new ArrayList<>();
    boolean[][] f = new boolean[N][N];

    void init(String s)
    {
        ans.clear();
        for (int i = 0; i < N; ++i)
            Arrays.fill(f[i], false);

        int n = s.length();
        for (int len = 1; len <= n; ++len)//或者字符串哈希判断回文
            for (int l = 0; l + len - 1 < n; ++l)
                if (len == 1) f[l][l] = true;
                else if (len == 2 && s.charAt(l) == s.charAt(l + 1)) f[l][l + 1] = true;
                else if (len > 2)
                {
                    int r = l + len - 1;
                    f[l][r] = s.charAt(l) == s.charAt(r) && f[l + 1][r - 1];
                }
    }

    void dfs(int u, int cnt, int pre, String s)
    {
        if (u == cnt)
        {
            for (int i = 0; i < cnt; ++i)
                if (i == 0) temp.add(s.substring(0, path[0] + 1));
                else temp.add(s.substring(path[i - 1] + 1, path[i] + 1));
            if (path[cnt - 1] != s.length() - 1) temp.add(s.substring(path[cnt - 1] + 1));
            ans.add(new ArrayList<>(temp));
            temp.clear();
            return;
        }

        for (int i = pre + 1; i < s.length(); ++i)//从上一个位置+1开始选当前隔板
        {
            path[u] = i;
            if (u == 0 && !f[0][path[0]]) continue;//剪枝
            if (u != 0 && !f[path[u - 1] + 1][path[u]]) continue;
            if (u == cnt - 1 && i != s.length() - 1 && !f[i + 1][s.length() - 1]) continue;
            dfs(u + 1, cnt, i, s);
        }
    }

    public List<List<String>> partition(String s)
    {
        init(s);
        for (int i = 0; i < s.length(); ++i)
            dfs(0, i + 1, -1, s);
        return ans.stream().distinct().toList();
    }
}

2. 朴素dfs

class Solution
{
    static final int N = 20;
    final List<List<String>> ans = new ArrayList<>();
    final List<String> temp = new ArrayList<>();
    boolean[][] f = new boolean[N][N];

    void init(String s)
    {
        ans.clear();
        for (int i = 0; i < N; ++i)
            Arrays.fill(f[i], false);

        int n = s.length();
        for (int len = 1; len <= n; ++len)//或者字符串哈希判断回文
            for (int l = 0; l + len - 1 < n; ++l)
                if (len == 1) f[l][l] = true;
                else if (len == 2 && s.charAt(l) == s.charAt(l + 1)) f[l][l + 1] = true;
                else if (len > 2)
                {
                    int r = l + len - 1;
                    f[l][r] = s.charAt(l) == s.charAt(r) && f[l + 1][r - 1];
                }
    }

    void dfs(int cur, String s)
    {
        if (cur == s.length())
        {
            ans.add(new ArrayList<>(temp));
            return;
        }

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

    public List<List<String>> partition(String s)
    {
        init(s);
        dfs(0, s);
        return ans;
    }
}

class Solution
{
    int n;
    char[] str;
    int[] path = new int[20];//存储所有隔板
    int idx = 0;
    List<List<String>> ans = new ArrayList<>();

    boolean check(int l, int r)
    {
        while (l < r)
            if (str[l++] != str[r--])
                return false;
        return true;
    }

    String getV(int l, int r)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = l; i <= r; i++)
            sb.append((char) str[i]);
        return sb.toString();
    }

    void dfs(int p)//p是前一个挡板的位置
    {
        if (p == n - 1)
        {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < idx; i++)
                if (i == 0) list.add(getV(0, path[i]));
                else list.add(getV(path[i - 1] + 1, path[i]));
            ans.add(list);
            return;
        }

        for (int i = p + 1; i < n; i++)//枚举当前隔板选哪个
            if (check(p + 1, i))
            {
                path[idx++] = i;
                dfs(i);
                idx--;
            }

    }

    public List<List<String>> partition(String s)
    {
        n = s.length();
        str = s.toCharArray();
        dfs(-1);
        return ans;
    }
}