Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
题意：
拆分给定字符串，找到可将字符串分隔成回文substring的可能
思路：
backtracking枚举所有结果
容易掉坑：对于递归调用helper的时候，i+1 还是index+1 很容易就写错了！！！
代码：
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
List<String> path = new ArrayList<>();
helper(s, 0, path, result);
return result;
}
private void helper(String s, int index, List<String> path,List<List<String>> result){
if( index == s.length()){
result.add(new ArrayList<>(path));
}
for(int i = index ; i < s.length() ; i++){
if(isPalindrome(s, index, i)){ // 如果index--i 的这段串串是回文
path.add(s.substring(index, i+1));// 将index--i 的这段回文串串加到path里
helper(s, i+1, path, result); // 继续移动index递归生成可能的结果
path.remove(path.size() -1); //比如"baa" 从root 为'b'开始则先生成Arraylist ： 'b' + 'a' + 'a' 则要去掉最后一个元素'a'
// 再看 'b' + 'a' + '其他' 能新生成Arraylist
}
}
}
// 判断是否回文
private boolean isPalindrome(String s, int left, int right){
while (left < right){
if(s.charAt(left) != s.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
