7.分割回文串

• 2.13

  • start 虽然控制不回头，但不是一步一步➕的，而是上一个 for 里的 i+1的位置

• 2.3

  • 用 start 参数控制下一次回溯的起始位置（而不是为了不回头）（所以在回溯中需要当前位置 i+1 而不是 start+1）
  • substring 截取前 start 到 i+1 的位置

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

• 11.30
  • 就是经典回溯套路,这里需要start参数

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtrack(s,0);
        return res;
    }
    public void backtrack(String s,int start){
        if(start==s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=start;i<s.length();i++){
            if(!isPalindrome(s,start,i)) continue;//不是回文就剪枝
            path.add(s.substring(start,i+1));
            backtrack(s,i+1);
            path.remove(path.size()-1);
        }
    }
    public boolean isPalindrome(String s,int start,int end){
        while(start<end){
            if(s.charAt(start++)!=s.charAt(end--)) return false;
        }
        return true;
    }
}

• 回文判断时,需在循环中查看每个字符都符合最后才会返回true