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，繼續(xù)往下切，直到 start 越界

每次基于當前的 start，可以選擇不同的 i，切出 start 到 i 的子串，我們枚舉出這些選項 i：

• 切出的子串滿足回文，將它加入部分解 temp 數(shù)組，并繼續(xù)往下切（遞歸）
• 切出的子串不是回文，跳過該選擇，不落入遞歸，繼續(xù)下一輪迭代

結(jié)合動態(tài)規(guī)劃

其實，我們可以把所有子串是否回文，提前求出來，用二維數(shù)組存起來。回溯時，直接取 dp 數(shù)組中對應元素就好。

定義 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 是狀態(tài)轉(zhuǎn)移方程。

看看狀態(tài)轉(zhuǎn)移的方向，如下圖，幫助我們計算dp矩陣時選取掃描方向，合適的掃描方向，才不會出現(xiàn)：求當前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] 已經(jīng)做過的決定，放入了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