10-line 3ms O(1) solution with length check (7 <= n <= 39) Do not process IP of invalid length!


  • 0

    Key observation: By definition, valid IP address must have string between 7 and 39, so check length before any process.

    Then the algorithm will be straightforward, for each IP address token (i.e., '.' or ':'):

    • Check IP length in range
      • 2NblkIP.size()+1 ≤ Nblk(maxLblk + 1);
    • For each block s between tokens, check
      • block size: 1 ≤ s.size() ≤ maxLblk;
      • block digits are valid: s.find_first_not_of(digits[tk]) != string::npos;
      • for IPv4, check leading zero and value range: s[0] == '0' && s.size() > 1 || stoi(s) > 255
    • Check number of blocks.
        map<char, vector<int>> blk = {{'.', {4, 3}}, {':', {8, 4}}}; // token->{numBlock, maxBlockLen}
        map<char, string> digits = {{'.', "0123456789"},{':', "0123456789abcdefABCDEF"}}; // token->valid digits
        
        string validIPAddress(string& IP) {
          return checkAddress(IP, '.')? "IPv4" : checkAddress(IP, ':')? "IPv6" : "Neither";
        }
        
        bool checkAddress(const string& IP, char tk) { // check address for given token
          if (IP.size()+1 < 2*blk[tk][0] || IP.size()+1 > blk[tk][0]*(blk[tk][1]+1)) return false;
          stringstream ss(IP); string s;
          while (getline(ss, s, tk) && --blk[tk][0] >= 0) // check each block
            if (s.empty() || s.size() > blk[tk][1] || s.find_first_not_of(digits[tk]) != string::npos ||
                tk == '.' && (s[0] == '0' && s.size() > 1 || stoi(s) > 255)) return false; // special check for IPv4
    
          return blk[tk][0] == 0 && *IP.rbegin() != tk; // check block count and last char
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.