C++ not small, but easy to explain and understand.


  • 0
    S

    It is generating all combinations of 3 length string the ip address string.
    Checking whether substring generated is valid ip ie., <255
    Tricky case of numbers beginning with 0 needs to be handled.

    class Solution {
    public:
        vector<string> answer;
        set<string> allIps;
        
        void generateIp(int dots[], string ip,vector<int> nums){
            int i=0;
            string str ="";
            str +=to_string(nums[0]);
            str +='.';
            str +=to_string(nums[1]);
            str +='.';
            str +=to_string(nums[2]);
            str +='.';
            str +=to_string(nums[3]);
            if(allIps.find(str)==allIps.end()){
                allIps.insert(str);
                answer.push_back(str);
            }
        }
        
        void isValidIp(int dots[], string ip){
            if(dots[0]>3 || dots[1]-dots[0]>3 || dots[2]-dots[1]>3 || ip.length()-dots[2]>3) return;
            int i=0, num=0;
            vector<int> subs;
            string str="";
            while(i<dots[0]){
                num *=10;
                str +=ip[i];
                num +=ip[i++]-'0';
            }
            if(num>255 || (str[0]=='0' && str.length()!=1)) return;
            subs.push_back(num);
            num=0;
            str="";
            while(i<dots[1]){
                num *=10;
                str +=ip[i];
                num +=ip[i++]-'0';
            }
            if(num>255 || (str[0]=='0' && str.length()!=1)) return;
            subs.push_back(num);
            num=0;
            str="";
            while(i<dots[2]){
                num *=10;
                str +=ip[i];
                num +=ip[i++]-'0';
            }
            if(num>255 || (str[0]=='0' && str.length()!=1)) return;
            subs.push_back(num);
            num=0;
            str="";
            while(i<ip.length()){
                num *=10;
                str +=ip[i];
                num +=ip[i++]-'0';
            }
            if(num>255 || (str[0]=='0' && str.length()!=1)) return;
            subs.push_back(num);
            generateIp(dots,ip,subs);
        }
        
        void generateDots(int index, int dots[], int start, int end, string ip){
            
            if(index==3){
                isValidIp(dots, ip);
                return;
            }
            
            for(int i=start;i<=end;++i){
                dots[index] = i;
                generateDots(index+1, dots, i+1, end, ip);
            }
        }
        
        vector<string> restoreIpAddresses(string s) {
            if(s.length()>12) return answer;
            int dots[3] = {0};
            generateDots(0, dots, 1, s.length()-1, s);
            return answer;
        }
    };
    

Log in to reply
 

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