Given a strings, partitionssuch that every substring of the partition is a palindrome.
Return all possible palindrome partitioning ofs.
For example, givens="aab"
, Return
[
["aa","b"],
["a","a","b"]
]
Solution: 类似subset
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<List<String>>();
if(s == null){
return result;
}
List<String> path = new ArrayList<String>();
helper(s, result, path, 0);
return result;
}
private void helper(String s, List<List<String>> result, List<String> path, int start){
if(start == s.length()){
result.add(new ArrayList<String>(path));
return;
}
for(int i = start + 1; i <= s.length(); i++){
String prefix = s.substring(start, i);
if(!isPalindrome(prefix)){
continue;
}
path.add(prefix);
helper(s, result, path, i);
path.remove(path.size() - 1);
}
return;
}
private boolean isPalindrome(String s){
int i = 0, j = s.length() - 1;
while(i < j){
if(s.charAt(i) != s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}