My solution and explanation, improvement suggestion appreciated.


  • 0
    H

    Basically a DFS. Each node has at most 3 child which is selecting 1 digit, 2 digits and 3 digits. The constraints are its numeric value is smaller than 256. Apparently we only need to check this for for 3 digits child. Another constraint is that 0x, or 0xx is not allowed(this is known from test cases), so if the current remaining string starts with 0, we could only a 1-digit child.

    Temination: when we are about to fill the last part of the IP, check whether the remainder of the string is valid, if yes, add current path to the output.

    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) {
            if(s.empty()) return output;
            vector<string> x(4);
            DFS(0, x, s, 0);
            return output;
        }
        void DFS(int t, vector<string> &x, string &s, int i)
        {
            if(i>s.size()-1) return;
            if(t ==3)
            {
                if(s.size()-i>3 || (s[i]=='0' && i<s.size()-1)) //rule out digit number bigger than 3 and 0xx pattern
                    return;
                string remainder = s.substr(i);
                if(stoi(remainder)<256)
                {
                    x[t]=remainder;
                    string ip;
                    int k=0;
                    for(int j=0;j<7;j++)
                    {
                        if((j&1)==0)
                            ip.append(x[k++]);
                        else
                            ip.append(".");
                    }
                    output.push_back(ip);
                }
                return;
            }
            x[t]=s.substr(i,1);
            DFS(t+1,x,s,i+1);
            if(s[i]=='0') //don't include 0xx 
                return ;
            if(s.size()-i>=2)
            {
                x[t]=s.substr(i,2);
                DFS(t+1,x,s,i+2);
            }
            if(s.size()-i>=3 && stol(s.substr(i,3))<256)
            {
                x[t]=s.substr(i,3);
                DFS(t+1,x,s,i+3);
            }
        }
    private:
        vector<string> output;
    };

Log in to reply
 

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