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)

思路：

DFS。只需增加判断每个部分数字在0到255之间，并且第一位数不能是0.

另外代码中用到string转int的方法，先利用c_str()转成C string，再用atoi()与atof()。

代码：

 1     vector<string> result;
 2     string tmp;
 3     void search(int step, string s){
 4         int l = s.length();
 5         if(l > (5-step)*3 || l < (5-step))
 6             return;
 7         if(step == 4){
 8             if(s[0] == '0' && s.length() > 1)
 9                 return ;
10             int t = atoi(s.c_str());
11             if(t >= 0 && t <= 255){
12                 tmp = tmp + "." + s;
13                 result.push_back(tmp);
14             }
15             return;
16         }
17         if(l > 3)
18             l = 3;
19         if(s[0] == '0')
20             l = 1;
21         for(int i = 1; i <= l; i++){
22             string s1 = s.substr(0, i);
23             string s2 = s.substr(i);
24             int t = atoi(s1.c_str());
25             if(t >= 0 && t <= 255){
26                 string pre = tmp;
27                 if(tmp == ""){
28                     tmp = s1;
29                     search(step+1, s2);
30                     tmp = "";
31                 }
32                 else{
33                     tmp = tmp + "." + s1;
34                     search(step+1, s2);
35                     tmp = pre;
36                 }                
37             }
38         }
39     }
40     vector<string> restoreIpAddresses(string s) {
41         // IMPORTANT: Please reset any member data you declared, as
42         // the same Solution instance will be reused for each test case.
43         result.clear();
44         tmp = "";
45         search(1, s);
46         return result;
47     }