leetcode93 Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

 1 class Solution {
 2 public:
 3     vector<string> restoreIpAddresses(string s) {
 4         vector<string> ans;
 5         vector<int> cur(8,0);
 6         dep(ans,s,0,cur,0);
 7         return ans;
 8     }
 9     
10     void dep(vector<string> &ans,string s,int ps,vector<int>&cur,int pc)
11     {
12         int len=s.length();
13         for(int i=1;i<=3;i++)
14         {
15             if(ps+i<=len)
16             {
17                 if(judge(s.substr(ps,i)))
18                 {
19                     cur[pc]=ps;
20                     cur[pc+1]=i;
21                     if(ps+i==len&&pc==6)
22                         addstr(ans,s,cur);
23                     else if(ps+i!=len&&pc!=6)
24                         dep(ans,s,ps+i,cur,pc+2);
25                 }
26             }
27         }
28     }
29     
30     bool judge(string str)
31     {
32         if(str.length()>1&&str[0]=='0')
33             return false;
34         int temp=atoi(str.c_str());
35         if(temp>=0&&temp<=255)
36             return true;
37         return false;
38     }
39     
40     void addstr(vector<string> &ans,string s,vector<int>&cur)
41     {
42         string temp="";
43         temp+=s.substr(cur[0],cur[1]);
44         temp+=".";
45         temp+=s.substr(cur[2],cur[3]);
46         temp+=".";
47         temp+=s.substr(cur[4],cur[5]);
48         temp+=".";
49         temp+=s.substr(cur[6],cur[7]);
50         ans.push_back(temp);
51     }
52 };

View Code