LeetCode-131-分割回文串

131. 分割回文串

难度中等

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

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

示例 1：

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

示例 2：

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

提示：

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

思路

题意问的是，切分字符串s，切出的每一个子串必须是回文串，请找出所有切分的可能。

我们用指针 start 尝试着去切，切出一个回文串，基于新的 start，继续往下切，直到 start 越界

每次基于当前的 start，可以选择不同的 i，切出 start 到 i 的子串，我们枚举出这些选项 i：

• 切出的子串满足回文，将它加入部分解 temp 数组，并继续往下切（递归）
• 切出的子串不是回文，跳过该选择，不落入递归，继续下一轮迭代

结合动态规划

其实，我们可以把所有子串是否回文，提前求出来，用二维数组存起来。回溯时，直接取 dp 数组中对应元素就好。

定义 dp 子问题：dp[i][j]：从 i 到 j 的子串是否回文。

dp[i][j]为真，罗列出所有的情况：

i == j时，子串只有一个字符，肯定回文
j-i == 1时，子串由两个字符组成，字符必须相同s[i] == s[j]
j-i > 1时，子串由两个以上字符组成，s[i] == s[j]，且dp[i+1][j-1]=true即除去首尾字符的剩余子串也是回文子串。
1、2 是 base case，如下图的蓝、粉格子，不需要递推出来，3 是状态转移方程。

看看状态转移的方向，如下图，帮助我们计算dp矩阵时选取扫描方向，合适的扫描方向，才不会出现：求当前dp[i][j]时，它所依赖的dp[i+1][j-1]还没求出来。

image-20210614123351632

class Solution {
    public static List<List<String>> partition(String s) {
        // dp[L][R] -> 是不是回文
        boolean[][] dp = getdp(s.toCharArray());
        LinkedList<String> path = new LinkedList<>();
        List<List<String>> ans = new ArrayList<>();
        process(s, 0, path, dp, ans);
        return ans;
    }

    public static boolean[][] getdp(char[] str) {
        int N = str.length;
        boolean[][] dp = new boolean[N][N];
        for (int i = 0; i < N - 1; i++) {
            dp[i][i] = true;
            dp[i][i + 1] = str[i] == str[i + 1];
        }
        dp[N - 1][N - 1] = true;
        for (int j = 2; j < N; j++) {
            int row = 0;
            int col = j;
            while (row < N && col < N) {
                dp[row][col] = str[row] == str[col] && dp[row + 1][col - 1];
                row++;
                col++;
            }
        }
        return dp;
    }

    // s 字符串
    // s[0...index-1] 已经做过的决定，放入了path中
    // 在index开始做属于这个位置的决定，
    // index == s.len  path之前做的决定（一种分割方法），放进总答案ans里
    public static void process(String s, int index, LinkedList<String> path, 
            boolean[][] dp, List<List<String>> ans) {
        if (index == s.length()) {
            ans.add(copy(path));
        } else {
            for (int end = index; end < s.length(); end++) {
                // index..index   
                // index..index+1
                // index..index+2
                // index..end
                if (dp[index][end]) {
                    path.addLast(s.substring(index, end + 1));
                    process(s, end + 1, path, dp, ans);
                    path.pollLast();
                }
            }
        }
    }

    public static List<String> copy(List<String> path) {
        List<String> ans = new ArrayList<>();
        for (String p : path) {
            ans.add(p);
        }
        return ans;
    }
}

image-20210614220547271