package com.geeksforgeeks.Interesting;

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

/**
 * Created by Vaidehi Murarka on 3/4/2017.
 */
public class RestoreIpAddress {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if(s == null || s.length() < 4){
            return result;
        }
        for(int i = 1; i < 4; i++){
            String first = s.substring(0, i);
            if(isValid(first)){
                for(int j = 1; j < 4 && i+j < s.length(); j++){
                    String second = s.substring(i, i+j);
                    if(isValid(second)){
                        for(int k = 1; k < 4 && i + j + k < s.length(); k++ ){
                            String third = s.substring(i+j, i+j+k);
                            String forth = s.substring(i+j+k);
                            if( isValid(third) && isValid(forth) ){
                                result.add( first + "." + second + "." + third + "." + forth );
                            }
                        }
                    }
                }
            }
        }

        return result;

    }

    private boolean isValid(String s){

        if(s.length() > 3){
            return false;
        }

        if(s.charAt(0) == '0' && s.length() > 1 ){
            return false;
        }

        long value = Long.parseLong(s);
        if(value <= 255 && value >= 0) {
            return true;
        }
        return false;
    }
    public static void main(String[] args){
        RestoreIpAddress restoreIpAddress = new RestoreIpAddress();
        System.out.println(restoreIpAddress.restoreIpAddresses("25525511135"));
    }
}
