Restore IP Addresses

Problem:
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)

Analysis:
It's very similar to palindrome-partitioning, but implementation has to be very careful with corner cases. 
Solution:
items.size() > 4 is critical to backtrack. 
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s.length() < 4 || s == null) return res;

        helper(res, new ArrayList<>(), s);
        return res;
    }

    private void helper (List<String> res, List<String> items, String s) {
        if (items.size() == 4 && s.length() == 0) {
            res.add(convert(items));
            return;
        }
        
        if (items.size() > 4 ) return;
        
        for (int i = 0; i < 3 && i < s.length(); i++) {
            String item = s.substring(0, i + 1);
            if ((item.charAt(0) == '0' && item.length() > 1) || 
                 Integer.parseInt(item) > 255) continue;
            items.add(item);
            helper(res, items, s.substring(i+1));
            items.remove(items.size() - 1);
        }
    }

    private String convert(List<String> items) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 4; i++) {
            String s = items.get(i);
            if (i == 3) sb.append(s);
            else sb.append(s + ".");
        }
        return sb.toString();
    }
}

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array