Sharing my C++ solution


  • 0
    T
    class Solution {
    private:
        void restoreIpAddressesHelper(string& s, int iword, int iS, string& temp, vector<string>& result)
        {
            int nS = s.length();
            if(iword==4 && iS == nS){
                result.push_back(temp);
            }
            if(iword==4 || iS==nS)
                return;
                
            for(int count=1; count<=3; count++)
            {
                if((4-iword-1<=nS-iS-count) && (3*(4-iword-1)>=nS-iS-count))
                {
                    string tmp = temp;
                    if(s[iS]=='0')
                    {
                        temp = temp + "0.";
                        restoreIpAddressesHelper(s, iword+1, iS+1, temp, result);
                        temp = tmp;
                        break;
                    }
                    
                    else if(count==3)
                    {
                        string tmpStr = s.substr(iS, count);
                        int tmpNum = atoi(tmpStr.c_str());
                        if(tmpNum<256)
                        {
                            temp = temp+tmpStr;
                            temp = temp + '.';
                            restoreIpAddressesHelper(s, iword+1, iS+3, temp, result);
                            temp = tmp;
                        }
                    }
                    else
                    {
                        string tmpString = s.substr(iS, count);
                        temp = temp + tmpString;
                        temp = temp + '.';
                        restoreIpAddressesHelper(s, iword+1, iS+count, temp, result);
                        temp = tmp;
                    }
                }
            }
        }
        
    public:
        vector<string> restoreIpAddresses(string s) {
            string temp;
            vector<string> result;
            restoreIpAddressesHelper(s, 0, 0, temp, result);
            for(int i=0; i<result.size(); i++)
            {
                result[i].pop_back();
            }
                
            return result;
        }
    };

Log in to reply
 

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