leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0093.cpp (1296B)

      1 class Solution {
      2     bool valid(const string &s) {
      3         if (s.empty()) return true;
      4         return stoi(s) >= 0 && stoi(s) <= 255;
      5     }
      6 
      7   public:
      8     vector<string> restoreIpAddresses(string s) {
      9         int n = s.size();
     10 
     11         vector<string> res;
     12         string s1, s2, s3, s4;
     13         bool e4;
     14 
     15         s1 = "";
     16         for (int i = 0; i < n; i++) {
     17             s1 += s[i], s2 = "";
     18             if (!valid(s1)) break;
     19             for (int j = i + 1; j < n; j++) {
     20                 s2 += s[j], s3 = "";
     21                 if (!valid(s2)) break;
     22                 for (int k = j + 1; k < n; k++) {
     23                     s3 += s[k], s4 = "";
     24                     if (!valid(s3)) break;
     25                     for (int l = k + 1; l < n; l++) {
     26                         s4 += s[l], e4 = false;
     27                         if (!valid(s4) || (s4.size() >= 2 && s4.front() == '0')) {
     28                             e4 = true;
     29                             break;
     30                         }
     31                     }
     32                     if (!e4 && !s4.empty()) res.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
     33                     if (s3.front() == '0') break;
     34                 }
     35                 if (s2.front() == '0') break;
     36             }
     37             if (s1.front() == '0') break;
     38         }
     39         return res;
     40     }
     41 };