实战训练1:Java解决LeetCode第131题 - 切分成回文子串的方法
最编程
2024-02-19 17:24:09
...
class Solution {
List<List<String>> res;
public List<List<String>> partition(String s) {
res=new ArrayList<>();
dfs(new ArrayList<String>(),s);
return res;
}
public void dfs(ArrayList<String> tmp,String s){
//剩下要处理的
if(s==null||s.length()==0){
res.add(new ArrayList(tmp));
return;
}
for(int i=1;i<=s.length();i++){
//a是已分割,b是未分割
String a=s.substring(0,i);
String b="";
if(i<s.length())
b=s.substring(i);
if(isPalindrome(a)){
tmp.add(a);
dfs(tmp,b);
tmp.remove(tmp.size()-1);
}
}
}
//判断是否是回文
public boolean isPalindrome(String s){
if(s.length()==0||s.length()==1) return true;
int i=0,j=s.length()-1;
while(i<=j){
if(s.charAt(i)!=s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
}