LeetCode: 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)

地址：

算法：递归构造。一个ip地址有四个数字，每个数字必须在0到255之间，并且不能第一个非零数字不能以零开头。基本的思想是，取最后一个数字，看其是否合理，如果合理在递归构造前面三个数字；取最后两个数字，如果合理在递归前面三个数字；取最后三个数字，如果合理在递归构造前面三个数字。代码：

1 class Solution { 2 public: 3     vector
        
          restoreIpAddresses(string s) { 4         vector
         
           result; 5         partitionIpAddresses(s,4,result); 6         return result; 7     } 8     bool partitionIpAddresses(string s, int n, vector
          
            &result){ 9         if(n <= 0 || s.empty()){10             return false;11         }12         if(n == 1){13             int val = atoi(s.c_str());14             if(val < 256 && isValidataion(s)){15                 result.push_back(s);16                 return true;17             }else{18                 return false;19             }20         }21         int i = s.size() - 1;22         int val = atoi(s.substr(i,1).c_str());23         vector
           
             temp;24         bool flag = partitionIpAddresses(s.substr(0,s.size()-1), n-1, temp);25         if(flag){26             for(int j = 0; j < temp.size(); ++j){27                 if(isValidataion(s.substr(i,1)))28                     result.push_back(temp[j] + "." + s.substr(i,1));29             }30         }31         temp.clear();32         --i;33         if(i >= 0){34             val = atoi(s.substr(i,2).c_str());35             flag = partitionIpAddresses(s.substr(0,s.size()-2), n-1, temp);36             if(flag){37                 for(int j = 0; j < temp.size(); ++j){38                     if(isValidataion(s.substr(i,2)))39                         result.push_back(temp[j] + "." + s.substr(i,2));40                 }41             }42         }43         temp.clear();44         --i;45         if(i >= 0){46             val = atoi(s.substr(i,3).c_str());47             if(val < 256){48                 flag = partitionIpAddresses(s.substr(0,s.size()-3), n-1, temp);49                 if(flag){50                     for(int j = 0; j < temp.size(); ++j){51                         if(isValidataion(s.substr(i,3)))52                             result.push_back(temp[j] + "." + s.substr(i,3));53                     }54                 }55             }56         }57         return !result.empty();58     }59     bool isValidataion(const string &s){60         if(s.size() < 1)    return false;61         if(s.size() == 1)   return true;62         if(s[0] == '0')     return false;63         return  true;64     }65 };