Validate IP Address

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

A valid IPv4 address is an IP in the form "x1.x2.x3.x4" where 0 <= xi <= 255 and xi cannot contain leading zeros. For example, "192.168.1.1" and "192.168.1.0" are valid IPv4 addresses while "192.168.01.1", "192.168.1.00", and "192.168@1.1" are invalid IPv4 addresses.

A valid IPv6 address is an IP in the form "x1:x2:x3:x4:x5:x6:x7:x8" where:

1. 1 <= xi.length <= 4
2. xi is a hexadecimal string which may contain digits, lowercase English letter ('a' to 'f') and upper-case English letters ('A' to 'F').
3. Leading zeros are allowed in xi.

For example, "2001:0db8:85a3:0000:0000:8a2e:0370:7334" and "2001:db8:85a3:0:0:8A2E:0370:7334" are valid IPv6 addresses, while "2001:0db8:85a3::8A2E:037j:7334" and "02001:0db8:85a3:0000:0000:8a2e:0370:7334" are invalid IPv6 addresses.

Examples:

1. Input: queryIP = "172.16.254.1" Output: "IPv4"
2. Input: queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334" Output: "IPv6"
3. Input: queryIP = "256.256.256.256" Output: "Neither"

class Solution:
    def validIPAddress(self, queryIP: str) -> str:
        def is_ipv4(ip):
            parts = ip.split('.')
            if len(parts) != 4:
                return False
            for part in parts:
                if not part.isdigit():
                    return False
                if part[0] == '0' and len(part) > 1:
                    return False
                try:
                    num = int(part)
                    if num < 0 or num > 255:
                        return False
                except ValueError:
                    return False
            return True
        
        def is_ipv6(ip):
            parts = ip.split(':')
            if len(parts) != 8:
                return False
            for part in parts:
                if not (1 <= len(part) <= 4):
                    return False
                try:
                    int(part, 16)
                except ValueError:
                    return False
            return True
        
        if '.' in queryIP:
            if is_ipv4(queryIP):
                return "IPv4"
            else:
                return "Neither"
        elif ':' in queryIP:
            if is_ipv6(queryIP):
                return "IPv6"
            else:
                return "Neither"
        else:
            return "Neither"

Explanation:

The solution is structured as follows:

1. validIPAddress(queryIP: str) -> str Function:

   • This is the main function that takes an input string queryIP and returns "IPv4", "IPv6", or "Neither" based on whether the input is a valid IPv4 address, a valid IPv6 address, or neither.
   • It first checks if the IP contains "." (IPv4) or ":" (IPv6) to determine which validation function to use.

2. is_ipv4(ip) Function:

   • Splits the IP address by "." into parts.
   • Checks if there are exactly four parts.
   • Iterates through each part:
     • Verifies if each part is a digit.
     • Validates no leading zeros, unless the part is just "0".
     • Parses the part as an integer and verifies if it's within the range of 0 to 255.
   • Returns True if all conditions are met; otherwise, False.

3. is_ipv6(ip) Function:

   • Splits the IP address by ":" into parts.
   • Checks if there are exactly eight parts.
   • Iterates through each part:
     • Checks if the length of each part is between 1 and 4.
     • Verifies if each part is a valid hexadecimal string.
   • Returns True if all conditions are met; otherwise, False.

Naive Solution:

A basic approach would involve using regular expressions to validate both IPv4 and IPv6 addresses. However, this could be less readable and maintainable.

Optimal Solution:

The current solution is optimal in terms of readability and efficiency. It avoids using regular expressions, which can be slower, and explicitly checks the validity conditions for IPv4 and IPv6 addresses.

Big(O) Run-time Analysis:

• IPv4 Validation:
  • Splitting the string by "." takes O(n) time, where n is the length of the input string.
  • Iterating through the four parts takes O(1) time since it's always four parts.
  • The digit and range checks take O(1) time.
  • Total: O(n) for splitting + O(1) for checks = O(n).
• IPv6 Validation:
  • Splitting the string by ":" takes O(n) time, where n is the length of the input string.
  • Iterating through the eight parts takes O(1) time since it's always eight parts.
  • The length and hexadecimal checks take O(1) time.
  • Total: O(n) for splitting + O(1) for checks = O(n).
• Overall: The validIPAddress function calls either is_ipv4 or is_ipv6, so the overall time complexity is O(n), where n is the length of the input queryIP string.

Big(O) Space Usage Analysis:

• IPv4 Validation:
  • The parts list stores four string segments, so it takes O(1) space.
  • Other variables take O(1) space.
  • Total: O(1).
• IPv6 Validation:
  • The parts list stores eight string segments, so it takes O(1) space.
  • Other variables take O(1) space.
  • Total: O(1).
• Overall: The validIPAddress function uses O(1) space, as the space required does not scale with the input size. The space needed for splitting the string is fixed because the IP addresses have a fixed number of components (4 for IPv4 and 8 for IPv6).

Edge Cases:

1. Empty String:

   • Input: ""
   • Output: "Neither"
   • Handled by the initial checks that either "." or ":" must be present.

2. Invalid Characters:

   • Input: "192.168.1.a"
   • Output: "Neither"
   • Handled by the isdigit() check in the is_ipv4 function and the int(part, 16) check in the is_ipv6 function, which will raise a ValueError for invalid characters.

3. Leading Zeros in IPv4:

   • Input: "192.168.01.1"
   • Output: "Neither"
   • Handled by the if part[0] == '0' and len(part) > 1: check in the is_ipv4 function.

4. Out of Range Values in IPv4:

   • Input: "256.256.256.256"
   • Output: "Neither"
   • Handled by the if num < 0 or num > 255: check in the is_ipv4 function.

5. Invalid Lengths in IPv6:

   • Input: "2001:0db8:85a3:0:0:8A2E:0370:73345"
   • Output: "Neither"
   • Handled by the if not (1 <= len(part) <= 4): check in the is_ipv6 function.

6. Incorrect Number of Parts:

   • Input: "192.168.1" (IPv4 with only 3 parts)
   • Output: "Neither"
   • Input: "2001:0db8:85a3:0:0:8A2E:0370" (IPv6 with only 7 parts)
   • Output: "Neither"
   • Handled by checking if len(parts) != 4: for IPv4 and if len(parts) != 8: for IPv6.