Poison

93. Restore IP Addresses

发表于 
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
49
50
51
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ipList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>(4);
        backtrack(ipList, numList, s, 0);
        return ipList;
    }

    private void backtrack(List<String> ipList, List<Integer> numList, String s, int startIndex) {
        if (startIndex == s.length()) {
            if (numList.size() == 4) {
                StringBuilder sb = new StringBuilder();
                sb.append(numList.get(0)).append(".");
                sb.append(numList.get(1)).append(".");
                sb.append(numList.get(2)).append(".");
                sb.append(numList.get(3));
                ipList.add(sb.toString());
            }

            return;
        }

        char c = s.charAt(startIndex);
        if (c == '0') {
            numList.add(0);
            backtrack(ipList, numList, s, startIndex + 1);
            numList.remove(numList.size() - 1);
        } else {
            int num = c - '0';
            numList.add(num);
            backtrack(ipList, numList, s, startIndex + 1);
            numList.remove(numList.size() - 1);

            if (startIndex + 1 < s.length()) {
                num = num * 10 + (s.charAt(startIndex + 1) - '0');
                numList.add(num);
                backtrack(ipList, numList, s, startIndex + 2);
                numList.remove(numList.size() - 1);
            }

            if (startIndex + 2 < s.length()) {
                num = num * 10 + (s.charAt(startIndex + 2) - '0');
                if (num <= 255) {
                    numList.add(num);
                    backtrack(ipList, numList, s, startIndex + 3);
                    numList.remove(numList.size() - 1);
                }
            }
        }
    }
}
Reference

93. Restore IP Addresses