Share 0ms neat and clear c++ solution using DFS


  • 12
    Z
    class Solution {
    public:
        vector<string> restoreIpAddresses(string s) {
            vector<string> result;
            string ip;
            dfs(s,0,0,ip,result); //paras:string s,start index of s,step(from0-3),intermediate ip,final result
            return result;
        }
        void dfs(string s,int start,int step,string ip,vector<string>& result){
            if(start==s.size()&&step==4){
                ip.erase(ip.end()-1); //remove the last '.' from the last decimal number
                result.push_back(ip);
                return;
            }
            if(s.size()-start>(4-step)*3) return;
            if(s.size()-start<(4-step)) return;
            int num=0;
            for(int i=start;i<start+3;i++){
                num=num*10+(s[i]-'0');
                if(num<=255){
                    ip+=s[i];
                    dfs(s,i+1,step+1,ip+'.',result);
                }
                if(num==0) break;
            }
        }
    };

Log in to reply
 

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