简介

切割问题和组合问题相差不大，切割问题可以巧妙的转化为组合问题，套用组合问题的模板和剪枝技巧。

131.分割回文串

题目描述

解题思路

递归函数参数

全局变量数组path存放切割后回文的子串，二维数组result存放结果集。（这两个参数可以放到函数参数里）
本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。

递归函数终止条件

党startIndex到达字符串的最后时，停止切割。

单层搜索的逻辑

来看看在递归循环，中如何截取子串呢？
在for (int i = startIndex; i < s.size(); i++)循环中，我们定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在vector path中，path用来记录切割过的回文子串。

public List<List<String>> partition(String s) {
    backtracking(s, 0);
    return res;
}
List<List<String>> res = new ArrayList<>();   // 记录所有组合结果
LinkedList<String> path = new LinkedList<>(); // 记录一条路径
public void backtracking(String s, int startIndex) {
    // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
    if (startIndex >= s.length()) { // 注意是等于也算，最后一层递归就是=
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = startIndex; i < s.length(); i++) {
        // 先判断是否为回文字串
        if (isPalindrome(s, startIndex, i)) {
            path.add(s.substring(startIndex, i + 1));  // 是回文字串则添加进去
        } else {
            continue;   // 不是回文字串则查找下一个
        }
        backtracking(s, i + 1);
        path.removeLast();
    }
}
public boolean isPalindrome(String s, int start, int end) {
    int i, j;
    char[] chars = s.toCharArray();
    for (i = start, j = end; i < j; i++, j--) { // 双指针法判断回文数
        if (chars[i] != chars[j]) {
            return false;
        }
    }
    return true;
}

93.复原IP地址

题目描述

解题思路

递归参数

startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
本题我们还需要一个变量pointNum，记录添加逗点的数量。

递归终止条件

终止条件和131.分割回文串情况就不同了，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。
然后验证一下第四段是否合法，如果合法就加入到结果集里

单层搜索的逻辑

在每层如果有数字符合IP段的要求（也就是isValid函数返回为true），那么就加入一个 ‘.’ 在s字符串中，pointNum加一，回溯也就是去掉字符串的 ‘.’ ，pointNum减一。不合法直接break，后面的肯定都不合法，所以直接break，不是continue。

注意：需要判断ip是否大于12位。

public List<String> restoreIpAddresses(String s) {
    if (s.length() > 12) {  // 大于12位，不满足
        return res;
    }
    backtracking(s, 0, 0);
    return res;
}
List<String> res = new ArrayList<>();
public void backtracking(String s, int startIndex, int pointNum) {
    if (pointNum == 3) {    // 当 "." 的数量等于三时,退出循环
        // 此时判断最后一个字符串是否满足要求
        if (isValid(s, startIndex, s.length() - 1)) {
            res.add(s);
        }
        return;
    }
    for (int i = startIndex; i < s.length(); i++) {
        if (isValid(s, startIndex, i)) {    // 由于判断时的左闭右闭区间
            s = s.substring(0, i + 1) + "." + s.substring(i + 1);   // i的后面加入一个"."
            pointNum++;
            backtracking(s, i + 2, pointNum);
            pointNum--; // 回溯
            s = s.substring(0, i + 1) + s.substring(i + 2); // 去掉逗号
        } else {
            break;  // 不合法，直接退出循环
        }
    }
}
/**
         * 判断字符串在左闭右闭的区间是否合法
         *
         * @param s
         * @param start
         * @param end
         * @return
         */
public boolean isValid(String s, int start, int end) {
    if (start > end) {
        return false;
    }
    if (s.charAt(start) == '0' && start != end) {   // 0开头的数字不合法
        return false;
    }
    int sum = 0;
    for (int i = start; i <= end; i++) {
        if (s.charAt(i) > '9' || s.charAt(i) < '0') {   // 为非法字符
            return false;
        }
        sum = sum * 10 + (s.charAt(i) - '0');   // 请总和
    }
    if (sum > 255) {    // 大于255不满足
        return false;
    }
    return true;
}