class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> list = new ArrayList<String>();
        for(int i = 0;i<s.length()-2 && i<4;i++) {
            for(int j = i+1;j<s.length()-1 && j<4+i;j++) {
                for(int k = j+1;k<s.length() && j<4+k;k++) {
                    String a = s.substring(0,i);
                    String b = s.substring(i,j);
                    String c = s.substring(j,k);
                    String d = s.substring(k,s.length());
                    if(isValid(a) && isValid(b) && isValid(c) && isValid(d)) {
                        System.out.println(a+"."+b+"."+c+"."+d);
                        list.add(a+"."+b+"."+c+"."+d);
                    }
                }
            }
        }
        return list;
    }
    
    public boolean isValid(String str) {
        if(str.length() == 0 || (str.charAt(0) == '0'&&str.length()>1) || str.length() > 3 || Integer.parseInt(str) > 255) {
            return false;
        }
        return true;
    }
}