RestoreIpAddresses.java

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses {
    static void restoreIpAddresses(String s, List<String> result, String ip, int count, int index) {
        if (count > 4) { return; }
        if (count == 4 && ip.length() == (s.length() + 3)) {
            result.add(ip);
        }

        for (int i = 1; i <= 3; i++) {
            if (index + i > s.length()) { break; }
            String sub = s.substring(index, index + i);
            if ((sub.charAt(0) == '0' && i > 1) || (Integer.parseInt(sub) > 255 && i == 3)) {
                continue;
            }
            String next = ip + sub + (count == 3 ? "" : ".");
            restoreIpAddresses(s, result, next, count + 1, index + i);
        }
    }

    static List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList();
        if (s.isEmpty()) { return result; }
        restoreIpAddresses(s, result, "", 0, 0);
        return result;
    }

    public static void main(String[] args) {
        String s;
        s = "25525511135";
        System.out.println(restoreIpAddresses(s));
        s = "0000";
        System.out.println(restoreIpAddresses(s));
    }
}