代码随想录day23 Java版

131.分割回文串

开幕雷击，感觉挺难的，需要把切割问题抽象为组合问题，还得设置切割过的地方不能重复切割，所以递归函数需要传入i + 1。

模拟切割线，其实就是index是上一层已经确定了的分割线，i是这一层试图寻找的新分割线

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        backtrack(s,0);
        return res;
    }
    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)) {
                String str = s.substring(start, i + 1);
                path.addLast(str);
            } else {
                continue;
            }
            backtrack(s, i + 1);
            path.removeLast();
        }
    }
    
    boolean isPalindrome(String s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }
}

93.复原IP地址

比较考字符串操作，回溯比较容易

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        backTracking(sb, 0, 0);
        return res;
    }
    void backTracking(StringBuilder s, int start, int dotCount){
        if(dotCount == 3){
            if(isValid(s, start, s.length() - 1)){
                res.add(s.toString());
            }
            return;
        }
        for(int i = start; i < s.length(); i++){
            if(isValid(s, start, i)){
                s.insert(i + 1, '.');
                backTracking(s, i + 2, dotCount + 1);
                s.deleteCharAt(i + 1);
            }else{
                break;
            }
        }
    }
    boolean isValid(StringBuilder s, int start, int end){
        if(start > end) return false;
        if(s.charAt(start) == '0' && start != end) return false;
        int num = 0;
        for(int i = start; i <= end; i++){
            int digit = s.charAt(i) - '0';
            num = num * 10 + digit;
            if(num > 255) return false;
        }
        return true;
    }
}

78.子集

可以注释掉 if (start >= nums.length) return; 这行代码，因为、在每一次递归调用中，都会先将当前的 path 加入到结果集中，然后再进行下一层的递归搜索。当 start >= nums.length 时，for 循环条件不满足，递归就自然会结束。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums,0);
        return res;
    }
    void backtrack(int[] nums, int start) {
        res.add(new ArrayList<>(path));
        //if (start >= nums.length) return;
        for(int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i+1);
            path.removeLast();
        }
    }
}

90.子集II

和前一天的组合数去重一个套路，理解了树层去重和树枝去重

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0){
            res.add(path);
            return res;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtrack(nums, 0);
        return res;
    }
    void backtrack(int[] nums, int start) {
        res.add(new ArrayList<>(path));
        //if (start >= nums.length) return;
        for(int i = start; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            path.add(nums[i]);
            used[i] = true;
            backtrack(nums, i+1);
            path.removeLast();
            used[i] = false;
        }
    }
}