本題考察的是深度優(yōu)先搜索+回溯+回文串判斷
題目描述
給定一個字符串 s原叮，將 s 分割成一些子串，使每個子串都是回文串符匾。
返回 s 所有可能的分割方案蕴潦。
示例:
輸入: "aab"
輸出:
[
["aa","b"],
["a","a","b"]
]
題目思考+算法分析
1.本題需要將所有的分割方法都找出來，所以肯定需要用到DFS（深度優(yōu)先搜索）或者BFS（廣度優(yōu)先搜索）
2.每一個字符串都可以分為兩部分：左邊一個回文串加右邊一個子串汪榔，比如"abc"可分為"a"+"bc"蒲拉。然后對"bc"分割仍然是同樣的方法，分為"b"+"c"痴腌。
3.優(yōu)先尋找更短的回文串雌团，然后回溯找稍微長一些的回文串分割方法，不斷回溯士聪，分割锦援，直到找到所有的分割方法。
比如剥悟，分割"aac"灵寺，
(1)分割為 a + ac
(2)分割為 a + a+ c，分割完成懦胞，得到一組結果替久，回溯到a+ ac
(3)a+ ac中ac不是回文串，繼續(xù)回溯躏尉，回溯到 aac
(4)分割為稍長的回文串蚯根，分割為 aa+c 分割完成得到一組結果，回溯到aac
(5)aac不會回文串，搜索完成
所以颅拦，本題的解法就是深度優(yōu)先搜索+回文串判斷+回溯
代碼
java 7ms 85%
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
if(s==null||s.length()==0)
return res;
DFS_ReCall(s,new ArrayList<String>(),0);
return res;
}
/**
* 深度優(yōu)先搜索(優(yōu)先搜索長度短的回文串)+回溯(搜索所有長度的回文串)
*/
public void DFS_ReCall(String s,List<String> remain,int left){
if(left==s.length()){ //判斷終止條件
res.add(new ArrayList<String>(remain)); //添加到結果中
return;
}
for(int right=left;right<s.length();right++){ //從left開始蒂誉，依次判斷l(xiāng)eft->right是不是回文串
if(isPalindroom(s,left,right)){ //判斷是否是回文串
remain.add(s.substring(left,right+1)); //添加到當前回文串到list中
DFS_ReCall(s,remain,right+1); //從right+1開始繼續(xù)遞歸，尋找回文串
remain.remove(remain.size()-1); //回溯距帅，從而尋找更長的回文串
}
}
}
/**
* 判斷字符串s的子串(left->right)是否是回文串
*/
public boolean isPalindroom(String s,int left,int right){
while(left<right&&s.charAt(left)==s.charAt(right)){
left++;
right--;
}
return left>=right;
}
}
