LeetCode--Restore IP Addresses

dfs即可
注意边界情况：
（1）s长度不在4 和 12之间
（2）"010"这种形式是错误的
 1 class Solution {
 2 public:
 3     vector<string> restoreIpAddresses(string s) {
 4         vector<string> res;
 5         if(s.length() < 4 || s.length() > 12){
 6             return res;
 7         }
 8         
 9         dfs(s,"",res,0);
10         return res;
11     }
12     void dfs(string ip,string tmpres,vector<string> &res,int cnt){
13         if(cnt == 3 && isvalid(ip)){
14             string tmp = tmpres+ip;
15             res.push_back(tmp);
16             return;
17         }
18         for(int i = 1 ; i < 4 && i < ip.length() ; ++i){
19             string tmp = ip.substr(0,i);
20             if(isvalid(tmp)){
21                 dfs(ip.substr(i),tmpres+tmp+".",res,cnt+1);
22             }
23         }
24     }
25     bool isvalid(string str){
26         if(str.length() <= 0)
27             return false;
28         int tmp = atoi(str.c_str());
29         if(str[0] == '0'){
30             if(str == "0"){
31                 return true;
32             }
33             else
34             {
35                 return false;
36             }
37         }
38         if(tmp <= 255 && tmp > 0){
39             return true;
40         }
41         return false;
42     }
43 };