T131、分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]

解

回溯求解。从前向后依次遍历字符串，然后判断每次划分结果是否是回文串，如果不是则跳过本次回溯。

 public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        int len = s.length();
        if(len <= 0)
            return res;
        Deque<String> stack = new ArrayDeque<>();
        backtrace(s,0,s.length(),stack,res);
        return res;
    }
    
    public void backtrace(String s, int start, int len, Deque<String> path, List<List<String>> res){
        if(start == len){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i < len; i++){
            if(!check(s,start,i))
                continue;
            path.addLast(s.substring(start,i+1));
            backtrace(s,i+1,len,path,res);
            path.removeLast();
        }
    }
    public boolean check(String s, int l, int r){
        while(l < r){
            if(s.charAt(l) != s.charAt(r))
                return false;
            l++;
            r--;
        }
        return true;
    }