Restore IP Addresses


  • 3

    How to solve this question? I have no idea. Please help me .


  • 0
    S

    Please select the right sub-category. Are you asking for help on Restore IP Address or Two Sum? Since you chose the Two Sum sub-category and your question is Restore IP Address.


  • 6
    C

    In my opinion, this is a backtracing problem, this means you have to iterate all possible valid combination.
    Below are my Solutions, hope this will demonstrate clear what the algorithms goes.

     public ArrayList<String> restoreIpAddresses(String s) {
            // Start typing your Java solution below
            // DO NOT write main() function
        	ArrayList<String> result=new ArrayList<String>();
            helper(s, 0,"",result);
            return result;
        }
        
        public void helper(String dataSegment,int level,String temp,ArrayList<String> result){
        	if(level==4){
        		if(dataSegment.length()==0)
        			result.add(temp.substring(1));
        		return;
        	}
        	int possi=dataSegment.length()>=3?3:dataSegment.length();
        	for(int i=1;i<=possi;i++){
        		String newOne=dataSegment.substring(0,i);
        		if(isValidSegment(newOne)){
        			temp+="."+newOne;
        			helper(dataSegment.substring(i), level+1, temp,result);
        			temp=temp.substring(0,temp.lastIndexOf("."));
        		}
        	}
        }
        
        public boolean isValidSegment(String s){
        	if(s.charAt(0)=='0')
        		return s.length()==1;
        	Integer result=Integer.parseInt(s);
        	if(result>255)
        		return false;
        	return true;
        }

  • 0
    S

    please edit your code in right format.


  • 0
    S

    I have updated your question category. Hope you be careful next time.


  • 0
    C

    I`ve modified it.


  • 6
    S

    Here is a solution from old discuss by soulmachine . Thanks to soulmachine !

    I have translated and made a little modification to his post.
    General thought of this problem is generate all possible combination of given string by recursion and check if it is a valid ip address, but there are also some optimization in the recursion process.

    Hope going thru his code with its detailed comment will help you understand the algorithm to this problem.

    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) {
            vector<string> result;
            string ip; // save temporary result in processing
            dfs(s, 0, 0, ip, result);
            return result;
        }
    
        /**
         * @brief: split the string
         * @param[in] s string,input
         * @param[in] startIndex, start from which index in s
         * @param[in] step current step index,start from 0,valid values: 0,1,2,3,4, as special, 4 means ending of split
         * @param[out] intermediate, split result in current spliting process
         * @param[out] result, save all possible IP address
         * @return none
         */
        void dfs(string s, size_t start, size_t step, string ip,
                vector<string> &result) {
            if (start == s.size() && step == 4) {  // find a possible result
                ip.resize(ip.size() - 1);
                result.push_back(ip);
                return;
            }
    
            // since each part of IP address is in 0..255, the length will not more than 3, and not less than 1 as well.
            if (s.size() - start > (4 - step) * 3)
                return;  // optimize, the length of rest part of s string should not more than 3 * remaining part count need to split. 
            if (s.size() - start < (4 - step))
                return;  // optimize, the length of rest part of s string should not less than 1 * remaining part count need to split. 
    
            int num = 0;
            for (size_t i = start; i < start + 3; i++) {
                num = num * 10 + (s[i] - '0');
    
                if (num <= 255) {  // current split is valid, go to next recursion.
                    ip += s[i];
                    dfs(s, i + 1, step + 1, ip + '.', result);
                }
                if (num == 0) break;  // single 0 is allowed, but '00' is forbidden.
            }
        }
    };
    

  • 13
    U

    Actually, you can do 3 for-loops loops to check all points' position.

    @1337c0d3r @Shangrila

    Following is more detail. You can get points' positions by i, j, k. Using these positions, you can divide s into candidate ip-form. Then, you can judge whether the candidate fits ip.
    To improve the efficiency, you can narrow the scope of i, j, k.

    for (int i = 1; i <= s.len - 3; i ++) {
         for (int j = i + 1; j <= s.len - 2; j ++) {
               for (int k = j + 1; k <= s.len - 1; k ++) {
                       // Here, i, j, k are the three points' position.
               }
         }
    }
    

  • 0

    This doesn't seem like an answer. Is this intended to be a comment? If it is, could you please delete this and add it as a comment instead?


  • 0
    S

    Could you please detail your answer? like how the 3 loop runs and how to check?


  • 0
    S

    Cool! I like it!!! This solution is more elegant than recursion! However it is restricted to split ip address, which only 4 parts!

    Thanks for sharing!


  • 14
    M

    Based on @user20 suggestion, using 3 for-loops

    vector<string> restoreIpAddress(string s)  {
        vector<string> res;
        if (s.size() > 12 || s.size() < 4)
             return res;
    
        for (int i=1; i<4; i++) {
            string first = s.substr(0, i);
            if (!isValid(first))
                continue;
            for (int j=1; i+j < s.size() && j<4; j++) {
                string second = s.substr(i, j);
                if (!isValid(second))
                    continue;
                for (int k=1; i+j+k < s.size() && k<4; k++) {
                    string third = s.substr(i+j, k);
                    string fourth = s.substr(i+j+k);
                    if (isValid(third) && isValid(fourth)) {
                        string temp = first+"."+second+"."+third+"."+fourth;
                        res.push_back(temp);
                    }
                }
            }
        }
        
        return res;
    }
    
    bool isValid(string s) {
        if (s.size() > 1 && s[0] == '0')
            return false;
        if (stoi(s) <= 255 && stoi(s) >= 0)
            return true;
        else
            return false;
    }

  • 0
    Y

    I think there is a typo in your solution.

    for(size_t i = start; i<start+3; i++){
    ......
    }

    has potential for index out of bound exception. You need to add one more piece of logic
    i<start+3 && i<s.size()


  • 1
    S

    Solution in Java, use 3 for loop:

    public class Solution {
    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> result = new ArrayList<String>();
        String tempIP = null;
        for (int i = 1;i<s.length();i++){
            if(i<=3&&(s.length()-i)<=9&&(s.length()-i)>=3){
                for (int j=i+1;j<s.length();j++){
                    if(j-i<=3&&(s.length()-j)<=6&&(s.length()-i)>=2){
                        for (int k=j+1;k<s.length();k++){
                            if ((k-j)<=3&&(s.length()-k)<=3){
                            	String n1 = s.substring(0, i);
                            	String n2 = s.substring(i, j);
                            	String n3 = s.substring(j, k);
                            	String n4 = s.substring(k, s.length());
                            	if (!(n1.charAt(0) =='0'&& n1.length()>1)&&
                            	 !(n2.charAt(0) =='0'&& n2.length()>1)&&
                            	 !(n3.charAt(0) =='0'&& n3.length()>1)&&
                            	 !(n4.charAt(0) =='0'&& n4.length()>1)&&
                            	 Integer.parseInt(n1)<256&&Integer.parseInt(n2)<256&&
                            	 Integer.parseInt(n3)<256&&Integer.parseInt(n4)<256){
                                    tempIP = n1+"."+n2+"."+n3+"."+n4;
                                    result.add(tempIP);
                            	}
                            }
                        }
                    }
                }
            }
        }
        return result;
    }
    

    }


  • 0
    W

    I solve the problem in a way like your solution.


  • 0
    R
    This post is deleted!

  • 1
    S

    Please say something around your solution, not only code, while you are sharing your great solution.


  • 2
    V

    Recursive version using Back Tracking.It is needed to insert 3 dots to divide the string, and need to make sure that IP address is valid..

    Valid IP Address: less than or equal to 255, greater or equal to 0

                            "0X" or "00X" is not valid.
    

    Sub net refers to the part of Ip address separated by a '.', in the string 255.255.324.54 there are four sub nets 255, 255, 324, 54.

    For this one, the length of each sub net is from 1 to 3. We use a vector<string> to store each part, and cut the input string every time and append '.' for the first three sub nets, and then append the last sub net and do it recursively

    Time complexity cannot be defined in big Oh notation as it tries to find the time complexity asymptotically but here the size of input is fixed between 4 and 12, and relative to input which is of constant size,the time taken by this program doesn't go linearly with the size of input, in fact if one plot a graph by taking input string length on X axis(values from 4 to 12 only) and and time complexity on Y axis the graph would be a straight line.

    Space complexity cannot be defined in big Oh notation because relative to input string length of fixed size the size of the output list is also fixed in length .

    class Solution {
    public:
        bool valid(string str){
            //value of subnet must be in range 0 to 255
            if (str.size()==3 && stoi(str)>255){return false;}
            //00X is invalid
            if (str.size()==3 && str[0]=='0'){return false;}
            //0X is invalid
            if (str.size()==2 && str[0]=='0'){return false;}
            return true;
        }
        
        void getIpAddresses(string s, string IpAddress, vector<string> &IpAddresses, int subnetLength){
            if (subnetLength==0){
                //sinput string is completely traversed add Ip address to list
                if (s.empty()){IpAddresses.push_back(IpAddress);}
                return;
                
            }else{
                for (int i=1;i<=3;i++){
                    //check for the validity of the subnet
                    if (s.size()>=i && valid(s.substr(0,i))){
                        //for the last subnet (subnetLength = 1)  '.' shouldn't be appended
                        if (subnetLength==1){getIpAddresses(s.substr(i),IpAddress+s.substr(0,i),IpAddresses,subnetLength-1);}
                        //for the subnets 2,3,4 the first three subnets '.' need to be appended.
                        else{getIpAddresses(s.substr(i),IpAddress+s.substr(0,i)+".",IpAddresses,subnetLength-1);}
                    }
                }
            }
        }
        
        vector<string> restoreIpAddresses(string s) {
            vector<string> IpAddresses;
            //subnetLength helps to decide whether to append '.'  or not last subnet shouldn't end with '.'
            int subnetLength = 4;
            getIpAddresses(s,"",IpAddresses,subnetLength);
            return IpAddresses;
        }
    };

  • 0
    B

    It's my solution with java.It's based enumerate all the possible.

    public class Solution {
        public List<String> restoreIpAddresses(String s) {
        	List<String> res = new ArrayList<String>();
            for(int i = 1; i < s.length(); ++i){
            	if(Integer.valueOf(s.substring(0, i))>255) break;
            	if(i != 1 &&s.charAt(0) == '0') continue;
            	for(int j = i+1; j < s.length(); ++j){
            		if(Integer.valueOf(s.substring(i, j))>255) break;
            		if(j-i != 1 &&s.charAt(i) == '0') continue;
            		for(int k = j+1; k < s.length(); ++k){
            			if(Integer.valueOf(s.substring(j, k))>255) break;
            			if(k-j != 1 &&s.charAt(j) == '0') continue;
            			try{
            				Integer.valueOf(s.substring(k));
            			}catch(Exception e){
            				continue;
            			}
            			if(Integer.valueOf(s.substring(k))>255){
            				continue;
            			}
            			if(s.length()-k != 1 &&s.charAt(k) == '0') continue;
            			res.add(s.substring(0, i)+"."+s.substring(i, j)+"."+s.substring(j, k)
            					+"."+s.substring(k));
            		}
            	}
            }
            return res;
        }
    }

  • 0
    N

    nice answer!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.