Restore IP Addresses

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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)

代码：

 class Solution {  
 public:  
   vector<string> restoreIpAddresses(string s) {  
     vector<string> result;  
     string ip;  
     restoreIpAddressHelper(s, result, ip, 0, 0);  
     return result;  
   }  
     
   void restoreIpAddressHelper(const string &s, vector<string> &result, string ip, int deep, int start) {  
     // pruning  
     if (s.size() - start > (4 - deep) * 3) return;  
     if (s.size() - start < 4 - deep) return;  
     if (deep == 4 && start == s.size()) {  
       ip.resize(ip.size() - 1);  
       result.push_back(ip);  
       return;  
     }  
     int num = 0;  
     for (int i = start; i < start + 3; ++i) {  
       num = num * 10 + s[i] - '0';  
       if (num > 255) break;  
       ip.push_back(s[i]);  
       restoreIpAddressHelper(s, result, ip + ".", deep + 1, i + 1);  
       if (num == 0) break; // case 0.0.0.0 or case 255.128.0.23  
     }  
   }  
 };