class Solution {
public:
    void dfs(vector<string> & vect,string str,int ptr,const string s,int lev)
    {
        if(lev >= 4 && ptr >= s.length())
            vect.push_back(str);
        if(ptr >= s.length() || lev >= 4 ) return ;
        int n = s[ptr] - '0';
        char tmp [4]={s[ptr++]},*p;
        p = tmp+1;
        if(lev)
            str += '.';
        while( n <= 255)
            {
                dfs(vect,str+string(tmp),ptr,s,lev+1);
                if(ptr >= s.length() || !n)
                    break;
                *(p++)=s[ptr];
                n = n*10 + s[ptr++]-'0';
            }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> vect;
        dfs(vect,"",0,s,0);
        return vect;
    }
};