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
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> list = new LinkedList<>();
        backtrack(s, list, new StringBuilder(), 0, 0);
        return list;
    }

    private void backtrack(String s, List<String> list, StringBuilder sb, int index, int level) {
        if (level > 4)
            return;
        if (index == s.length() && level == 4) {
            list.add(sb.toString());
            return;
        }
        for (int i = 1; i <= 3; i++) {
            if (index + i > s.length())
                break;
            int num = Integer.valueOf(s.substring(index, index + i));
            // Checking if num is 0~9 or 10~99 or 100 ~ 255 because leading 0s is invalid.
            if (i == 1 || i == 2 && num >= 10 && num <= 99 || i == 3 && num >= 100 && num <= 255) {
                sb.append(num);
                if (level < 3)
                    sb.append(".");
                backtrack(s, list, sb, index + i, level + 1);
                if (level < 3)
                    sb.deleteCharAt(sb.length() - 1);
                sb.delete(sb.length() - i, sb.length());
            }
        }
    }
}

虽然是backtrack但是处理的手法可以学习一下. 就是当前level可以取的数字的个数是1, 2, 3. 当然如果不够取的话就需要提前剪枝.

时间复杂度: O(1) 根据leetcode题解, 最多27种组合.
空间复杂度: O(1) 根据leetcode题解, 最多19种valid的组合.