題目描述（中等難度）
給一個(gè)字符串鸠儿，然后在任意位置切割若干次，保證切割后的每個(gè)字符串都是回文串进每。輸出所有滿足要求的切割結(jié)果命斧。
解法一 分治
將大問題分解為小問題，利用小問題的結(jié)果冯丙，解決當(dāng)前大問題。
這道題的話泞莉，舉個(gè)例子船殉。
aabb
先考慮在第 1 個(gè)位置切割，a | abb
這樣我們只需要知道 abb 的所有結(jié)果利虫，然后在所有結(jié)果的頭部把 a 加入
abb 的所有結(jié)果就是 [a b b] [a bb]
每個(gè)結(jié)果頭部加入 a堡僻，就是 [a a b b] [a a bb]
aabb
再考慮在第 2 個(gè)位置切割疫剃，aa | bb
這樣我們只需要知道 bb 的所有結(jié)果，然后在所有結(jié)果的頭部把 aa 加入
bb 的所有結(jié)果就是 [b b] [bb]
每個(gè)結(jié)果頭部加入 aa,就是 [aa b b] [aa bb]
aabb
再考慮在第 3 個(gè)位置切割牲阁，aab|b
因?yàn)?aab 不是回文串壤躲，所有直接跳過
aabb
再考慮在第 4 個(gè)位置切割，aabb |
因?yàn)?aabb 不是回文串凌唬，所有直接跳過
最后所有的結(jié)果就是所有的加起來
[a a b b] [a a bb] [aa b b] [aa bb]
然后中間的過程求 abb 的所有結(jié)果漏麦，求 aab 的所有結(jié)果等等客税，就可以遞歸的去求撕贞。遞歸出口的話，就是空串的所有子串就是一個(gè)空的list 即可麻掸。
public List<List<String>> partition(String s) {
return partitionHelper(s, 0);
}
private List<List<String>> partitionHelper(String s, int start) {
//遞歸出口赐纱，空字符串
if (start == s.length()) {
List<String> list = new ArrayList<>();
List<List<String>> ans = new ArrayList<>();
ans.add(list);
return ans;
}
List<List<String>> ans = new ArrayList<>();
for (int i = start; i < s.length(); i++) {
//當(dāng)前切割后是回文串才考慮
if (isPalindrome(s.substring(start, i + 1))) {
String left = s.substring(start, i + 1);
//遍歷后邊字符串的所有結(jié)果疙描，將當(dāng)前的字符串加到頭部
for (List<String> l : partitionHelper(s, i + 1)) {
l.add(0, left);
ans.add(l);
}
}
}
return ans;
}
private boolean isPalindrome(String s) {
int i = 0;
int j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
分治的話，一般情況下都可以利用動(dòng)態(tài)規(guī)劃的思想改為迭代的形式久又。遞歸就是壓棧壓棧效五，然后到達(dá)出口就出棧出棧出棧。動(dòng)態(tài)規(guī)劃就可以把壓棧的過程省去畏妖，直接從遞歸出口往回考慮戒劫。之前做過很多題了婆廊，可以參考 77題巫橄、91 題、115 題 等等湘换，都是一樣的思想。這道題修改的話贴浙，看完解法二的優(yōu)化后可以參考 這里 的代碼署恍。
解法二 分治優(yōu)化
每次判斷一個(gè)字符串是否是回文串的時(shí)候，我們都會(huì)調(diào)用 isPalindrome 判斷袁串。這就會(huì)造成一個(gè)問題呼巷，比如字符串 abbbba，期間我們肯定會(huì)判斷 bbbb 是不是回文串破镰，也會(huì)判斷 abbbba 是不是回文串压储。判斷 abbbba 是不是回文串的時(shí)候，在 isPalindrome 中依舊會(huì)判斷中間的 bbbb 部分集惋。而其實(shí)如果我們已經(jīng)知道了 bbbb 是回文串刮刑，只需要判斷 abbbba 的開頭和末尾字符是否相等即可。
所以我們?yōu)榱吮苊庖恍┲貜?fù)判斷雷绢，可以用動(dòng)態(tài)規(guī)劃的方法，把所有字符是否是回文串提前存起來胶惰。
對于字符串 s霞溪。
用 dp[i][j] 表示 s[i中捆，j] 是否是回文串坊饶。
然后有 dp[i][j] = s[i] == s[j] && dp[i+1][j-1] 。
我們只需要兩層 for 循環(huán)蟋滴，從每個(gè)下標(biāo)開始痘绎，考慮所有長度的子串即可。
boolean[][] dp = new boolean[s.length()][s.length()];
int length = s.length();
//考慮所有長度的子串
for (int len = 1; len <= length; len++) {
//從每個(gè)下標(biāo)開始
for (int i = 0; i <= s.length() - len; i++) {
int j = i + len - 1;
dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);
}
}
因?yàn)橐ＷC dp[i + 1][j - 1] 中 i + 1 <= j - 1尔苦，
i + 1 <= j - 1
把 j = i + len - 1 代入上式
i + 1 <= i + len - 1 - 1
化簡得
len >= 3
所以為了保證正確行施，多加了 len < 3 的條件。也就意味著長度是 1 和 2 的時(shí)候稠项，我們只需要判斷 s[i] == s[j]鲜结。
然后把 dp 傳入到遞歸函數(shù)中即可。
public List<List<String>> partition(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int length = s.length();
for (int len = 1; len <= length; len++) {
for (int i = 0; i <= s.length() - len; i++) {
int j = i + len - 1;
dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]);
}
}
return partitionHelper(s, 0, dp);
}
private List<List<String>> partitionHelper(String s, int start, boolean[][] dp) {
if (start == s.length()) {
List<String> list = new ArrayList<>();
List<List<String>> ans = new ArrayList<>();
ans.add(list);
return ans;
}
List<List<String>> ans = new ArrayList<>();
for (int i = start; i < s.length(); i++) {
if (dp[start][i]) {
String left = s.substring(start, i + 1);
for (List<String> l : partitionHelper(s, i + 1, dp)) {
l.add(0, left);
ans.add(l);
}
}
}
return ans;
}
解法三 回溯
115 題 中考慮了分治乐疆、回溯贬养、動(dòng)態(tài)規(guī)劃误算，這道題同樣可以用回溯法迷殿。
回溯法其實(shí)就是一個(gè) dfs 的過程，同樣舉個(gè)例子庆寺。
aabb
先考慮在第 1 個(gè)位置切割，a | abb
把 a 加入到結(jié)果中 [a]
然后考慮 abb
先考慮在第 1 個(gè)位置切割知纷，a | bb
把 a 加入到結(jié)果中 [a a]
然后考慮 bb
先考慮在第 1 個(gè)位置切割，b | b
把 b 加入到結(jié)果中 [a a b]
然后考慮 b
先考慮在第 1 個(gè)位置切割伍绳，b |
把 b 加入到結(jié)果中 [a a b b]
然后考慮空串
把結(jié)果加到最終結(jié)果中 [[a a b b]]
回溯到上一層
考慮 bb
考慮在第 2 個(gè)位置切割乍桂，bb |
把 bb 加入到結(jié)果中 [a a bb]
然后考慮 空串
把結(jié)果加到最終結(jié)果中 [[a a b b] [a a bb]]
然后繼續(xù)回溯
可以看做下邊的圖做 dfs ，而每一層其實(shí)就是當(dāng)前字符串所有可能的回文子串权谁。
就是很經(jīng)典的回溯法憋沿，一個(gè) for 循環(huán)，添加元素甥绿，遞歸则披，刪除元素。這里判斷是否是回文串图谷，我們就直接用 dp 數(shù)組阱洪。
public List<List<String>> partition(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int length = s.length();
for (int len = 1; len <= length; len++) {
for (int i = 0; i <= s.length() - len; i++) {
dp[i][i + len - 1] = s.charAt(i) == s.charAt(i + len - 1) && (len < 3 || dp[i + 1][i + len - 2]);
}
}
List<List<String>> ans = new ArrayList<>();
partitionHelper(s, 0, dp, new ArrayList<>(), ans);
return ans;
}
private void partitionHelper(String s, int start, boolean[][] dp, List<String> temp, List<List<String>> res) {
//到了空串就加到最終的結(jié)果中
if (start == s.length()) {
res.add(new ArrayList<>(temp));
}
//在不同位置切割
for (int i = start; i < s.length(); i++) {
//如果是回文串就加到結(jié)果中
if (dp[start][i]) {
String left = s.substring(start, i + 1);
temp.add(left);
partitionHelper(s, i + 1, dp, temp, res);
temp.remove(temp.size() - 1);
}
}
}
總
這道題沒有什么新內(nèi)容了，就是分治承璃、回溯蚌本、動(dòng)態(tài)規(guī)劃，很常規(guī)的題目了舷嗡。
更多詳細(xì)通俗題解詳見 leetcode.wang 嵌莉。
