restore IP address

restore IP address

Easy problem

Atention:

  • length of the string.
  • leading zero of each part.
Try to cut the string into 4 pieces and check if ever part is valid.
 1 class Solution {
 2 public:
 3     vector<string> restoreIpAddresses(string s) {
 4         vector<string> result;
 5         result.clear();
 6         int n = s.length();
 7         if ( n < 4 || n > 12 ) {
 8             return result;
 9         }
10         for ( int i = 1; i < 4 && i < n ; i++ ) {
11             for ( int j = i+1; j < i+4 && j < n; j++ ) {
12                 for ( int k = j+1; k < j+4 && k < n; k++ ) {
13                     string sub1 = s.substr(0,i);
14                     if ( "-1" == validIp(sub1) ) {
15                         continue;
16                     }
17                     string sub2 = s.substr(i,j-i);
18                     if ( "-1" == validIp(sub2) ) {
19                         continue;
20                     }
21                     string sub3 = s.substr(j,k-j);
22                     if ( "-1" == validIp(sub3) ) {
23                         continue;
24                     }
25                     string sub4 = s.substr(k,n-k);
26                     if ( "-1" == validIp(sub4) ) {
27                         continue;
28                     }
29                     result.push_back(sub1+"."+sub2+"."+sub3+"."+sub4);
30                 }
31             }
32         }
33         return result;
34     }
35     string validIp( string a ) {
36         if ( a[0] == '0' && a.length() > 1 ) {
37             return "-1";
38         }
39         int t = atoi(a.c_str());
40         if ( t < 0 || t > 255 ) {
41             return "-1";
42         } else {
43             return a;
44         }
45     }
46 };

Loading Disqus comments...
Table of Contents