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)

Solution: 注意各种条件: 1.0后面不能再接数,2.点不能加在最后,3.3个点的才正确

    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() < 4) {
            return ans;
        }
        helper(s, 0, 0, new StringBuilder(), ans, 0);
        return ans;
    }
    private void helper(String s, int index, int sum, StringBuilder path, List<String> ans, int count_of_dot) {
        if (index == s.length()) {
            if (count_of_dot == 3) {
                ans.add(path.toString());
            }            
            return;
        }
        sum = sum * 10 + s.charAt(index) - '0';
        if (sum > 255) {
            return;
        }
        path.append(s.charAt(index));
        if (sum > 0 || sum == 0 && index == s.length() - 1) {
            helper(s, index + 1, sum, path, ans, count_of_dot);
        }
        if (count_of_dot < 3 && index < s.length() - 1) {
            path.append('.');
            helper(s, index + 1, 0, path, ans, count_of_dot + 1);
            path.deleteCharAt(path.length() - 1);
        }
        path.deleteCharAt(path.length() - 1);
    }

results matching ""

    No results matching ""