思路:搜索分割点,每次判断当前分割点喝上一个分割点之间的数据是否为回文串,如果是,就继续搜索下一个。
(来实验室工作的第二天,加油!)
class Solution {
String str;
int len;
LinkedList<LinkedList<Integer>> list = new LinkedList<>();
public boolean check(String s){
// 判断s是否是回文字符串
if(s.length()==0 || s.length()==1){
return true;
}
return s.charAt(0)==s.charAt(s.length()-1) && check(s.substring(1,s.length()-1));
}
public void dfs(int splitIndex, LinkedList<Integer> tmp){
if(splitIndex==len+1){
list.add(new LinkedList<>(tmp));
return;
}
for(int i=splitIndex; i<len+1;i++){
int lastSplitIndex = 0;
if(tmp.size() != 0){
lastSplitIndex = tmp.get(tmp.size()-1);
}
String subStr = str.substring(lastSplitIndex, i);
if(check(subStr)){
tmp.add(i);
dfs(i+1, tmp);
tmp.removeLast();
}
}
return;
}
public List<List<String>> partition(String s) {
// 遍历切割点即可
this.str = s;
this.len = str.length();
LinkedList<Integer> tmp = new LinkedList<>();
dfs(1, tmp); //遍历切割点
// 将分割点转为字符串
List<List<String>> res = new LinkedList<>();
for(LinkedList<Integer> item: list){
List<String> res_item = new LinkedList<>();
int lastSplitIndex = 0;
for(int currentSplitIndex : item){
String subStr = str.substring(lastSplitIndex, currentSplitIndex);
res_item.add(subStr);
lastSplitIndex = currentSplitIndex;
}
res.add(res_item);
}
return res;
}
}