LeetCode-131-分割回文串
131. 分割回文串
難度中等
給你一個(gè)字符串 s产阱，請(qǐng)你將 s 分割成一些子串婉称，使每個(gè)子串都是 回文串 。返回 s 所有可能的分割方案构蹬。
回文串 是正著讀和反著讀都一樣的字符串王暗。
示例 1：
輸入：s = "aab"
輸出：[["a","a","b"],["aa","b"]]
示例 2：
輸入：s = "a"
輸出：[["a"]]
提示：
1 <= s.length <= 16-
s僅由小寫英文字母組成
思路
題意問的是，切分字符串s庄敛，切出的每一個(gè)子串必須是回文串俗壹，請(qǐng)找出所有切分的可能。
我們用指針 start 嘗試著去切藻烤，切出一個(gè)回文串绷雏，基于新的 start头滔，繼續(xù)往下切，直到 start 越界
每次基于當(dāng)前的 start涎显，可以選擇不同的 i坤检，切出 start 到 i 的子串，我們枚舉出這些選項(xiàng) i：
- 切出的子串滿足回文期吓，將它加入部分解 temp 數(shù)組早歇，并繼續(xù)往下切（遞歸）
- 切出的子串不是回文，跳過該選擇讨勤，不落入遞歸箭跳，繼續(xù)下一輪迭代
結(jié)合動(dòng)態(tài)規(guī)劃
其實(shí)，我們可以把所有子串是否回文潭千，提前求出來谱姓，用二維數(shù)組存起來∨偾纾回溯時(shí)屉来，直接取 dp 數(shù)組中對(duì)應(yīng)元素就好。
定義 dp 子問題：dp[i][j]：從 i 到 j 的子串是否回文狈癞。
dp[i][j]為真奶躯，羅列出所有的情況：
i == j時(shí)，子串只有一個(gè)字符亿驾，肯定回文
j-i == 1時(shí)，子串由兩個(gè)字符組成账嚎，字符必須相同s[i] == s[j]
j-i > 1時(shí)莫瞬，子串由兩個(gè)以上字符組成，s[i] == s[j]郭蕉，且dp[i+1][j-1]=true即除去首尾字符的剩余子串也是回文子串疼邀。
1、2 是 base case召锈，如下圖的藍(lán)旁振、粉格子，不需要遞推出來涨岁，3 是狀態(tài)轉(zhuǎn)移方程拐袜。
看看狀態(tài)轉(zhuǎn)移的方向，如下圖梢薪，幫助我們計(jì)算dp矩陣時(shí)選取掃描方向蹬铺，合適的掃描方向，才不會(huì)出現(xiàn)：求當(dāng)前dp[i][j]時(shí)秉撇，它所依賴的dp[i+1][j-1]還沒求出來甜攀。
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開始做屬于這個(gè)位置的決定，
// index == s.len path之前做的決定（一種分割方法）规阀，放進(jìn)總答案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;
}
}
