468. Validate IP Address - Leetcode Solution

Problem Description

The "Validate IP Address" problem asks you to write a function that determines whether a given string queryIP is a valid IPv4 address, a valid IPv6 address, or neither.

An IPv4 address consists of four decimal numbers, each ranging from 0 to 255, separated by periods (e.g., "172.16.254.1"). Leading zeros are not allowed.
An IPv6 address consists of eight groups of four hexadecimal digits, separated by colons (e.g., "2001:0db8:85a3:0000:0000:8a2e:0370:7334"). Each group can have 1 to 4 hexadecimal digits, and leading zeros are allowed.
If queryIP is a valid IPv4 address, return "IPv4".
If queryIP is a valid IPv6 address, return "IPv6".
If queryIP is neither, return "Neither".

Constraints: The input string queryIP will not be empty and will only contain characters permitted in IP addresses.

Thought Process

To solve this problem, we need to reliably distinguish between IPv4 and IPv6 formats and validate each according to its specific rules. The most direct approach is to check for the presence of '.' or ':' to determine which type the string might represent, then validate accordingly.

For IPv4, check that there are exactly four parts separated by periods, each part is a number between 0 and 255, and there are no leading zeros.
For IPv6, check that there are exactly eight groups separated by colons, each group has 1 to 4 valid hexadecimal digits, and only valid characters (0-9, a-f, A-F) are used.
For anything else, return "Neither".

A brute-force method would be to try all possible partitions, but that's unnecessary here. Instead, we can use string splitting and character validation to efficiently check the format.

Solution Approach

We divide the solution into the following steps:

Check for IPv4:
- Split the string by '.'. If there are not exactly 4 parts, it's not IPv4.
- For each part:
  - It must be non-empty.
  - It must contain only digits.
  - No leading zeros unless the part is "0".
  - Its integer value must be between 0 and 255.
Check for IPv6:
- Split the string by ':'. If there are not exactly 8 parts, it's not IPv6.
- For each part:
  - It must be non-empty and at most 4 characters.
  - All characters must be valid hexadecimal digits (0-9, a-f, A-F).
Return the result:
- If it passes IPv4 checks, return "IPv4".
- If it passes IPv6 checks, return "IPv6".
- Otherwise, return "Neither".

This approach is efficient because string splitting and validation are both fast and direct. We avoid unnecessary computations by short-circuiting as soon as a rule is broken.

Example Walkthrough

Let's walk through the input "172.16.254.1":

The string contains periods, so we attempt IPv4 validation.
Split by '.' gives ["172", "16", "254", "1"].
Each part:
- "172": digits only, no leading zero, 0 ≤ 172 ≤ 255
- "16": digits only, no leading zero, 0 ≤ 16 ≤ 255
- "254": digits only, no leading zero, 0 ≤ 254 ≤ 255
- "1": digits only, no leading zero, 0 ≤ 1 ≤ 255
All checks pass, so we return "IPv4".

Now, consider "2001:0db8:85a3:0000:0000:8a2e:0370:7334":

The string contains colons, so we attempt IPv6 validation.
Split by ':' gives 8 groups.
Each group is 1-4 hex digits, all characters are valid hexadecimal.
All checks pass, so we return "IPv6".

For "256.256.256.256":

Each part is a number, but 256 is out of the valid range (0-255).
Return "Neither".

Time and Space Complexity

Brute-force approach: If we tried all possible ways to split or parse the string, it would be very inefficient, possibly O(N^2) or worse.

Optimized approach (as above):

Splitting the string is O(N), where N is the length of the input.
Checking each part is O(1) (since there are at most 8 parts for IPv6).
So, the overall time complexity is O(N).
Space complexity is O(N) due to the space needed for the split parts.

Summary

We validated IP addresses by splitting the input string and checking each part according to IPv4 and IPv6 rules. The key is to apply the correct validation logic for each type and return the appropriate result. This method is efficient, easy to understand, and avoids unnecessary computation, making it an elegant solution to the problem.

Code Implementation

class Solution:
    def validIPAddress(self, queryIP: str) -> str:
        def isIPv4(IP):
            parts = IP.split('.')
            if len(parts) != 4:
                return False
            for part in parts:
                if not part or not part.isdigit():
                    return False
                if part[0] == '0' and len(part) != 1:
                    return False
                if not 0 <= int(part) <= 255:
                    return False
            return True

        def isIPv6(IP):
            parts = IP.split(':')
            if len(parts) != 8:
                return False
            hex_digits = '0123456789abcdefABCDEF'
            for part in parts:
                if not (1 <= len(part) <= 4):
                    return False
                for char in part:
                    if char not in hex_digits:
                        return False
            return True

        if queryIP.count('.') == 3 and isIPv4(queryIP):
            return "IPv4"
        elif queryIP.count(':') == 7 and isIPv6(queryIP):
            return "IPv6"
        else:
            return "Neither"

class Solution {
public:
    string validIPAddress(string queryIP) {
        if (queryIP.find('.') != string::npos) {
            if (isIPv4(queryIP)) return "IPv4";
        } else if (queryIP.find(':') != string::npos) {
            if (isIPv6(queryIP)) return "IPv6";
        }
        return "Neither";
    }
private:
    bool isIPv4(const string& IP) {
        vector<string> parts;
        string part;
        int cnt = 0;
        for (size_t i = 0; i <= IP.size(); ++i) {
            if (i == IP.size() || IP[i] == '.') {
                if (++cnt > 4) return false;
                if (part.empty() || part.size() > 3) return false;
                if (part[0] == '0' && part.size() != 1) return false;
                for (char c : part)
                    if (!isdigit(c)) return false;
                int num = stoi(part);
                if (num < 0 || num > 255) return false;
                parts.push_back(part);
                part.clear();
            } else {
                part += IP[i];
            }
        }
        return parts.size() == 4;
    }

    bool isIPv6(const string& IP) {
        vector<string> parts;
        string part;
        int cnt = 0;
        for (size_t i = 0; i <= IP.size(); ++i) {
            if (i == IP.size() || IP[i] == ':') {
                if (++cnt > 8) return false;
                if (part.empty() || part.size() > 4) return false;
                for (char c : part)
                    if (!isxdigit(c)) return false;
                parts.push_back(part);
                part.clear();
            } else {
                part += IP[i];
            }
        }
        return parts.size() == 8;
    }
};

class Solution {
    public String validIPAddress(String queryIP) {
        if (queryIP.chars().filter(c -> c == '.').count() == 3) {
            if (isIPv4(queryIP)) return "IPv4";
        } else if (queryIP.chars().filter(c -> c == ':').count() == 7) {
            if (isIPv6(queryIP)) return "IPv6";
        }
        return "Neither";
    }

    private boolean isIPv4(String IP) {
        String[] parts = IP.split("\\.", -1);
        if (parts.length != 4) return false;
        for (String part : parts) {
            if (part.length() == 0 || part.length() > 3) return false;
            if (part.charAt(0) == '0' && part.length() != 1) return false;
            for (char c : part.toCharArray())
                if (!Character.isDigit(c)) return false;
            try {
                int num = Integer.parseInt(part);
                if (num < 0 || num > 255) return false;
            } catch (NumberFormatException e) {
                return false;
            }
        }
        return true;
    }

    private boolean isIPv6(String IP) {
        String[] parts = IP.split(":", -1);
        if (parts.length != 8) return false;
        for (String part : parts) {
            if (part.length() == 0 || part.length() > 4) return false;
            for (char c : part.toCharArray()) {
                if (!isHexDigit(c)) return false;
            }
        }
        return true;
    }

    private boolean isHexDigit(char c) {
        return (c >= '0' && c <= '9') ||
               (c >= 'a' && c <= 'f') ||
               (c >= 'A' && c <= 'F');
    }
}

var validIPAddress = function(queryIP) {
    function isIPv4(IP) {
        let parts = IP.split('.');
        if (parts.length !== 4) return false;
        for (let part of parts) {
            if (part.length === 0 || (part[0] === '0' && part.length !== 1)) return false;
            if (!/^\d+$/.test(part)) return false;
            let num = Number(part);
            if (num < 0 || num > 255) return false;
        }
        return true;
    }
    function isIPv6(IP) {
        let parts = IP.split(':');
        if (parts.length !== 8) return false;
        let hex = /^[0-9a-fA-F]{1,4}$/;
        for (let part of parts) {
            if (!hex.test(part)) return false;
        }
        return true;
    }
    if (queryIP.split('.').length === 4 && isIPv4(queryIP)) {
        return "IPv4";
    } else if (queryIP.split(':').length === 8 && isIPv6(queryIP)) {
        return "IPv6";
    } else {
        return "Neither";
    }
};

AlgoMap.io

Want Help Cracking FAANG?