4ms C++ solution with explaination


  • 0
    A
    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) {
            vector<string> result;
            string path;
            helper(s,0,0,path,result);
            return result;
        }
        
       //s:    the input string
       //num:    the current processing part,IP address include 4 parts
       //pos:    the index of traversal character
       //path:    valid  IP address
       //result:    contain path
        void helper(string &s,int num,int pos,string &path,vector<string>& result)
        {
            //when the string is split to 4 parts.and the string traversal to the end
            if(pos==s.size()&&num==4)
            {
                //here should delete the last '.'
                result.push_back(path.substr(0,path.size()-1));
                return;
            }
            
            //if the remaining characters is greater than the max numbers of the remaining part
            if(s.size()-pos>3*(4-num))
                return;
                
            //if the part only include 1 character
            if(pos<s.size())
            {
                path+=s.substr(pos,1)+".";
                helper(s,num+1,pos+1,path,result);
                path=path.substr(0,path.size()-2);
            }
            
            //if the part include 2 characters
            if(pos<s.size()-1&&s[pos]!='0')
            {
                path+=s.substr(pos,2)+".";
                helper(s,num+1,pos+2,path,result);
                path=path.substr(0,path.size()-3);
            }
            
          //if the part include 3 characters
            if(pos<s.size()-2&&s[pos]!='0'&&s.substr(pos,3)<="255")
            {
                path+=s.substr(pos,3)+".";
                helper(s,num+1,pos+3,path,result);
                path=path.substr(0,path.size()-4);
            }
            
        }
    };

Log in to reply
 

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