LeetCode: Restore IP Addresses

LeetCode: 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
52

/**
 * Created by hzhou on 2015/5/26.
 * Email: [email protected]
 * <p>
 * Given a string containing only digits, restore it by returning all possible valid IP address combinations.
 * <p>
 * For example:
 * Given "25525511135",
 * <p>
 * return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
 */
public class RestoreIPAddresses {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() < 4) {
            return result;
        }
        helper(0, 0, s, result, "");
        return result;
    }
    private void helper(int count, int start, String s, List<String> result, String crt) {
        if (count == 3) {
            String sub = s.substring(start, s.length());
            if (isValid(sub)) {
                result.add(crt + sub);
            }
            return;
        }
        for (int i = start + 1; i < s.length() && i < start + 4; i++) {
            String sub = s.substring(start, i);
            if (isValid(sub)) {
                helper(count + 1, i, s, result, crt + sub + ".");
            }
        }
    }
    private boolean isValid(String s) {
        if (s == null || s.isEmpty() || (s.startsWith("0") && s.length() > 1)) {
            return false;
        }
        int result = 0;
        for (char c : s.toCharArray()) {
            result = 10 * result + c - '0';
        }
        return result >= 0 && result < 256;
    }
    @Test
    public void test() {
        String s = "25525511135";
        List<String> result = restoreIpAddresses(s);
    }
}