public class Solution {
    public static ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> list = new ArrayList<String>();
        int l = s.length();
        for (int i = 1; i <= 3; i++) {
            if (l - i > 9) continue;
            for (int j = i + 1; j <= i + 3; j++) {
                if (l - j > 6) continue;
                for (int k = j + 1; k <= j + 3; k++) {
                    if (l - k > 3 || l - k < 1) continue;
                    String s1 = s.substring(0, i);
                    String s2 = s.substring(i, j);
                    String s3 = s.substring(j, k);
                    String s4 = s.substring(k, l);
                    if (s1.length() > 1 && s1.charAt(0) == '0') continue;
                    if (s2.length() > 1 && s2.charAt(0) == '0') continue;
                    if (s3.length() > 1 && s3.charAt(0) == '0') continue;
                    if (s4.length() > 1 && s4.charAt(0) == '0') continue;
                    int n1 = Integer.parseInt(s1);
                    int n2 = Integer.parseInt(s2);
                    int n3 = Integer.parseInt(s3);
                    int n4 = Integer.parseInt(s4);
                    if (n1 > 255 || n2 > 255 || n3 > 255 || n4 > 255) continue;
                    String ip = s1 + "." + s2 + "." + s3 + "." + s4;
                    list.add(ip);
                }
            }
        }
        return list;
    }
}