【leetcode】Restore IP Addresses

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)

利用回溯法，注意几种情况：

0.0.0.0是合法的

01.1.1.1是不合法的

“10000”只能拆成10.0.0.0

 1 class Solution {
 2 public:
 3     vector<string> restoreIpAddresses(string s) {
 4        
 5         vector<string> result;
 6         string tmp="";
 7         bt(s,result);
 8         return result;
 9        
10     }
11    
12     void bt(string s,vector<string> &result,int start=0,string tmp="",int left=5)
13     {
14         left--;
15         int n=s.length();
16        
17         //找到的条件
18         if(left==0&&start==n)
19         {
20             //去除最后一个点
21             tmp.pop_back();
22             result.push_back(tmp);
23             return;
24         }
25        
26         //停止条件
27         if(left==0||(n-start)/left>3||(n-start)/left==0||start>n)
28         {
29             return;
30         }
31  
32        
33         string tmpStr;
34         if(n-start>=1)
35         {
36             tmpStr=tmp;
37             string str1=s.substr(start,1);
38             tmp+=str1;
39             bt(s,result,start+1,tmp+".",left);
40             tmp=tmpStr;
41         }
42        
43         if(n-start>=2&&s[start]!='0')
44         {
45             tmpStr=tmp;
46             string str2=s.substr(start,2);
47             tmp+=str2;
48             bt(s,result,start+2,tmp+".",left);
49             tmp=tmpStr;
50         }
51        
52         if(n-start>=3&&s[start]!='0')
53         {
54             tmpStr=tmp;
55             string str3=s.substr(start,3);
56             int n = atoi(str3.c_str());
57            
58             if(n<=255)
59             {
60                 tmp+=str3;
61                 bt(s,result,start+3,tmp+".",left);
62                 tmp=tmpStr;
63             }
64         }
65        
66     }
67 };