Restore IP Addresses(Medium)

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

解题思路：回溯+DFS

for循环每一层从一个字符开始取到3个字符，再加一个isValid的函数来验证取的字符是否是合法数字，如果是合法的数字，我们再进行下一层递归，否则跳过。

public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();

        if (s == null || s.length() < 4) {
            return result;
        }

        restoreHelper(s, 0, 1, "", result);

        return result;
}

private void restoreHelper(String s, int start, int segment, String curr, List<String> result) {
    if (start >= s.length()) {
        return;
    }

    if (segment == 4) {
        if (isValid(s.substring(start))) {
            result.add(curr + "." + s.substring(start));
        }
        return;
    }

    for (int i = 1; i < 4 && start + i < s.length(); i++) {
        String temp = s.substring(start, start + i);
        if (isValid(temp)) {
            if (segment == 1) {
                restoreHelper(s, start + i, segment + 1, temp, result);
            } else {
            restoreHelper(s, start + i, segment + 1, curr + "." + temp, result);
            }
        }
    }
}

private boolean isValid(String str) {
    if (str == null || str.length() > 3) {
        return false;
    }

    int num = Integer.parseInt(str);
    if (str.charAt(0) == '0' && str.length() > 1) {
        return false;
    }

    if (num >= 0 && num <= 255) {
        return true;
    }

    return false;
}