131.分割回文串

题目

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]

方法（回溯）

• 选择: 在决策树的每一个节点。我们可以做的选择为：只截取当前字符、截取当前字符和后一个字符、截取当前字符和后两个字符……截取当前字符和之后所有的字符。截取之后进行是否是回文的判断，如果是回文，则就是一个合理的选择。
• 路径：记录结果的path列表。
• 终止条件：遍历完了字符串s的每一个节点。

代码

List<List<String>> res = new LinkedList<>();
String s;
public List<List<String>> partition(String s) {
    this.s = s;
    backtrack(0, new LinkedList<>());
    return res;
}

public void backtrack(int start, List<String> path){
    if(start == s.length()){
        res.add(new LinkedList<>(path));
        return;
    }
    for(int i = start; i < s.length(); i++){
        if(!isPalindrome(start, i))
            continue;
        path.add(s.substring(start, i + 1));
        backtrack(i + 1, path);
        path.remove(path.size() - 1);
    }
}
public boolean isPalindrome(int start, int end){
    if(start < 0 && end > s.length() - 1 && start >= end)
        return false;
    int left = start;
    int right = end;
    while(left < right){
        if(s.charAt(left) != s.charAt(right))
            return false;
        left++;
        right--;
    }
    return true;
}