131.Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab"
,
Return
[
["aa","b"],
["a","a","b"]
]
方法
个人认为所有回文串的方法都可以用dfs或者dp的方式解决
本题在以dfs的框架下加上判断是否为回文串,若是回文串则执行相应的操作。
public class Solution {
List<List<String>> list = new ArrayList<List<String>>();
public List<List<String>> partition(String s) {
if(s == null || s.length() == 0){
return new ArrayList<List<String>>();
}
dfs(s,0,new ArrayList<String>());
return list;
}
public void dfs(String s, int start, ArrayList<String> arrayList){
if(start >= s.length()){
list.add(new ArrayList<String>(arrayList));
return;
}
for(int i = start; i < s.length(); i++){
if(isPal(s,start,i)){
if(start == i){
arrayList.add(Character.toString(s.charAt(start)));
}else{
arrayList.add(s.substring(start,i+1));
}
dfs(s, i+1, arrayList);
arrayList.remove(arrayList.size()-1);
}
}
}
public boolean isPal(String s, int start, int end){
while(start < end){
if(s.charAt(start) != s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}
}