综述

131. 分割回文串

枚举切割的点来得到分割方案

只有树枝上的子串是回文串时才能继续往下走，最后如果能够走到空串节点，就说明整个 s 完成了切分，也就是得到了一个合法的答案。

分割回文_lc131_tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {

    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return res;
    }

    private void backtracking(String s, int startIdx) {
        if (startIdx >= s.length()) {
            // base case，走到叶子节点
            // 即整个 s 被成功分割为若干个回文子串，记下答案
            res.add(new LinkedList<>(path));
            return;
        }

        for (int i = startIdx; i < s.length(); i++) {
            String cur = s.substring(startIdx, i + 1);
            if (isPalindrome(cur)) {
                // s[start..i] 是一个回文串，可以进行分割
                // 做选择，把 s[start..i] 放入路径列表中
                path.add(cur);
            } else {
                continue;
            }
            backtracking(s, i + 1);
            path.removeLast();
        }
    }

    private boolean isPalindrome(String str) {
        int s = 0, e = str.length() - 1;
        while (s < e) {
            if (str.charAt(s) != str.charAt(e)) {
                return false;
            }
            s++;
            e--;
        }
        return true;
    }
}

93. 复原 IP 地址

两个难点：

  1. 将问题转化为切割问题从而用回溯法来解决
    1. 如何造树
  2. 边界的处理
    1. base case
    2. 判断子字符串是否合法

对于第一个问题：

lc_93_复原IP_tres

对于第二个问题:

  1. base case
    1. 通过变量pointNum，记录添加逗点的数量。
1
2
3
4
5
6
7
if (pointCount == 3) {  // 逗点数量为3时，分隔结束
  // 判断第四段子字符串是否合法，如果合法就放进result中
    if (isValid(s, startIdx, s.length() - 1)) {
        res.add(s);
    }
    return;
}
  1. 切割出来的子字符串是否合法
    1. 段位以0为开头的数字不合法
    2. 段位里有非正整数字符不合法
    3. 段位如果大于255了不合法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private boolean isValid(String s, int start, int end) {
    if (start > end) return false;
    if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
        return false;
    }
    int num = 0;
    for (int i = start; i <= end; i++) {
        if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
            return false;
        }
        num = num * 10 + (s.charAt(i) - '0');
        if (num > 255) { // 如果⼤于255了不合法
            return false;
        }
    }
    return true;
}

综上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {

    List<String> res = new LinkedList<>();
    public List<String> restoreIpAddresses(String s) {
        backtracking(s, 0, 0);
        return res;
    }

    private void backtracking(String s, int startIdx, int pointCount) {
        if (pointCount == 3) {
            if (isValid(s, startIdx, s.length() - 1)) {
                res.add(s);
            }
            return;
        }

        for (int i = startIdx; i < s.length(); i++) {
            if (isValid(s, startIdx, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                pointCount++;
              	// 注意这里是 i + 2 由于加了一个 "."
                backtracking(s, i + 2, pointCount);
                pointCount--;
                s = s.substring(0, i + 1) + s.substring(i + 2);
            } else {
                break;
            }
        }
    }

    private boolean isValid(String s, int start, int end) {
        if (start > end) return false;
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }
}