LintCode: Restore IP Address

 1 class Solution {
 2 public:
 3     vector<string> restoreIpAddresses(string s) {
 4         vector<string> ret;
 5         if(s.size() > 12)
 6             return ret;
 7         for(int i = 0; i < s.size(); i ++)
 8         {// [0, i]
 9             string ip1 = s.substr(0, i+1);
10             if ( !check(ip1) ) break;
11             for(int j = i+1; j < s.size(); j ++)
12             {// [i+1, j]
13                 string ip2 = s.substr(i+1, j-i);
14                 if ( !check(ip2) ) break;
15                 for(int k = j+1; k < s.size()-1; k ++)
16                 {// [j+1, k], [k+1, s.size()-1]
17                     string ip3 = s.substr(j+1, k-j);
18                     string ip4 = s.substr(k+1);
19                     if(check(ip3) && check(ip4))
20                     {
21                         string ip = ip1 + "." + ip2 + "." + ip3 + "." + ip4;
22                         ret.push_back(ip);
23                     }
24                 }
25             }
26         }
27         return ret;
28     }
29     bool check(string ip)
30     {
31         int value = stoi(ip);
32         if(ip[0] == '0')    return ip.size() == 1;
33         return value <= 255 ? true : false;
34     }
35 };