Leetcode#93 Restore IP Addresses

DFS

注意以下几点：

1. IP地址中间的数字范围是0~255

2. IP地址中间的数字不能有前导0（0除外）

3. 如果原IP串长度超过12就不用做了，直接返回空

代码：

 1 vector<string> res;
 2     
 3 void dfs(string &s, vector<string> ans, int pos, int num) {
 4   if (pos == s.length() && num == 4) {
 5     res.push_back(ans[0] + "." + ans[1] + "." + ans[2] + "." + ans[3]);
 6     return;
 7   }
 8         
 9   for (int len = 1; len <= 3 && pos + len <= s.length(); len++) {
10     int v = 0;
11     bool pre0 = true;
12     for (int i = 0; i < len; i++) {
13       if (pre0 && s[pos + i] == '0')
14         break;
15       pre0 = false;
16       v = v * 10 + s[pos + i] - '0';
17     }
18     if ((len == 1 || !pre0) && v <= 255) {
19       ans.push_back(s.substr(pos, len));
20       dfs(s, ans, pos + len, num + 1);
21       ans.pop_back();
22     }
23   }
24 }
25     
26 vector<string> restoreIpAddresses(string s) {
27   if (s.length() <= 12)
28     dfs(s, vector<string>(), 0, 0);
29   return res;
30 }