这题乍一看有点像Decode Ways ，实际上是一个深搜+剪枝的题目

也可以通过三个for循环寻找可行的‘.’的位置

递归方法如下：

    vector
  
    restoreIpAddresses(string s) {
        vector
   
     res; restore(s, 0, 0, res, ""); return res; } void restore(string & s, int start, int ipNum, vector
    
      & res, string ip) { if (start == s.size() && ipNum == 4) { res.push_back(ip.substr(1)); return; } if (start >= s.size() || ipNum >= 4) return; if (s[start] == '0') return restore(s, start + 1, ipNum + 1, res, ip + "." + s.substr(start, 1)); if (s[start] == '1' || s[start] == '2') { if (!(s[start] == '2' && start + 1 < s.size() && (s[start + 1] > '5' || s[start + 1] == '5' && start + 2 < s.size() && s[start + 2] > '5'))) restore(s, start + 3, ipNum + 1, res, ip + "." + s.substr(start, 3)); } restore(s, start + 1, ipNum + 1, res, ip + "." + s.substr(start, 1)); restore(s, start + 2, ipNum + 1, res, ip + "." + s.substr(start, 2)); }