Clear c++ dfs solution


  • 0
    Y
    class Solution {
    public:
        vector<string> ans;
        vector<string> restoreIpAddresses(string s) {
            if(s.empty()||s.size()<4||s.size()>12)return ans;
            string str;
            dfs(s, 0, 1, str);
            return ans;
        }
        bool Isvalid(string s){
            if(s[0]=='0') return s.size() == 1;
            int num=stoi(s);
            return num<=255 && num>0;
        }
        void dfs(string &s, int start, int level, string str){
            if(level==4){
                string sub = s.substr(start);
                if(Isvalid(sub)){
                    ans.push_back(str+sub);
                }
                    return;
                }
            
            for (int i=1; i<=3 && (start+i)<s.size() ; i++) {
                string ip=s.substr(start, i);
                if(Isvalid(ip)){
                    string backup=str;
                    dfs(s, start+i, level+1, str+ip+'.');
                    str=backup;
                }
                else break;
            }
        
        }
        
        
    };

Log in to reply
 

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