algoadvance

Leetcode 468. Validate IP Address

Problem Statement

Given a string queryIP, return “IPv4” if queryIP is a valid IPv4 address, “IPv6” if queryIP is a valid IPv6 address or “Neither” if queryIP is not a correct IP of either type.

An IPv4 address is an address consisting of four numbers separated by dots, where each number is between 0 and 255 (inclusive) and cannot have leading zeros. Additionally, it’s a valid IPv4 address if and only if all four numbers are between 0 and 255 inclusive.

An IPv6 address is an address consisting of eight groups of four hexadecimal digits separated by colons. Each group is written using only hexadecimal digits (0-9, a-f, A-F) and can’t be empty.

Example:

Input: queryIP = "172.16.254.1"
Output: "IPv4"

Input: queryIP = "2001:0db8:85a3:0000:0000:8a2e:0370:7334"
Output: "IPv6"

Input: queryIP = "256.256.256.256"
Output: "Neither"

Clarifying Questions

  1. Should we handle cases where there are extra characters such as leading or trailing spaces?
    • Assume no leading or trailing spaces to simplify the problem.
  2. What if the input contains mixed characters that are not part of a valid IP address?
    • The output should be “Neither” in those cases.
  3. How to handle empty strings?
    • The output should be “Neither” for empty strings.

Strategy

  1. Check for IPv4:
    • Split the string by dots (.).
    • Check if there are exactly four parts.
    • Ensure each part is an integer between 0 and 255.
    • Ensure each part does not have leading zeros unless it is “0”.
  2. Check for IPv6:
    • Split the string by colons (:).
    • Check if there are exactly eight parts.
    • Ensure each part consists of 1 to 4 hexadecimal digits.
  3. If neither, return “Neither”.

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <cctype>

class Solution {
public:
    std::string validIPAddress(std::string queryIP) {
        if (isIPv4(queryIP)) return "IPv4";
        if (isIPv6(queryIP)) return "IPv6";
        return "Neither";
    }

private:
    bool isIPv4(const std::string& ip) {
        std::vector<std::string> parts = split(ip, '.');
        if (parts.size() != 4) return false;
        for (const std::string& part : parts) {
            if (part.empty() || part.size() > 3) return false;
            for (char c : part) {
                if (!isdigit(c)) return false;
            }
            int num = stoi(part);
            if (num < 0 || num > 255 || std::to_string(num) != part) return false;
        }
        return true;
    }

    bool isIPv6(const std::string& ip) {
        std::vector<std::string> parts = split(ip, ':');
        if (parts.size() != 8) return false;
        for (const std::string& part : parts) {
            if (part.empty() || part.size() > 4) return false;
            for (char c : part) {
                if (!isxdigit(c)) return false;
            }
        }
        return true;
    }

    std::vector<std::string> split(const std::string& s, char delim) {
        std::vector<std::string> elems;
        std::stringstream ss(s);
        std::string item;
        while (std::getline(ss, item, delim)) {
            elems.push_back(item);
        }
        return elems;
    }
};

Time Complexity

This solution thus efficiently checks the validity of the given IP address.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI