Validate IP Address

Patrick Leaton
Published: Aug. 2, 2021, 2 p.m.
Problem Description

Given a string IP, 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 xicannot contain leading zeros. For example, "192.168.1.1" and "192.168.1.0" are valid IPv4 addresses but "192.168.01.1", while "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 <= xi.length <= 4
  • xi is a hexadecimal string which may contain digits, lower-case English letter ('a'to 'f') and upper-case English letters ('A' to 'F').
  • 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.

 

Example 1:

Input: IP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

Input: IP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
Output: "IPv6"
Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

Input: IP = "256.256.256.256"
Output: "Neither"
Explanation: This is neither a IPv4 address nor a IPv6 address.

Example 4:

Input: IP = "2001:0db8:85a3:0:0:8A2E:0370:7334:"
Output: "Neither"

Example 5:

Input: IP = "1e1.4.5.6"
Output: "Neither"

 

Constraints:

  • IP consists only of English letters, digits and the characters '.' and ':'.

 

 

The description was taken from https://leetcode.com/problems/validate-ip-address/.

Problem Solution

#O(N) Time where N is characters in address, O(1) Space
class Solution:
    def validIPAddress(self, IP: str):
        
        def valid_IPV4(IP:str) -> bool:
            IP = IP.split(".")
            for num in IP:
                if not num:
                    return False
                if len(num) > 1 and num[0] == "0":
                    return False
                for digit in num:
                    if not digit.isdigit():
                        return False
                if int(num) < 0 or int(num) > 255:
                    return False
            return True
 
        def valid_IPV6(IP:str) -> bool:
            hexadecimals = '0123456789abcdefABCDEF'
            IP = IP.split(":")
            for num in IP:
                if len(num) == 0 or len(num) > 4:
                    return False
                for char in num:
                    if char not in hexadecimals:
                        return False
            return True
 
        if IP.count('.') == 3:
            if valid_IPV4(IP):
                return "IPv4"
            else:
                return "Neither"
        elif IP.count(":") == 7:
            if valid_IPV6(IP):
                return "IPv6"
            else:
                return "Neither"
        else:
            return "Neither"

Problem Explanation

String validation questions like this, Reorder Data in Log Files, Unique Email Addresses, etc., don't really have a trick to them or require a deep understanding of the algorithm used.  

They are more of just taking a practical string input, breaking it down into components, and processing the components.

Here, we are given a string and the string could either be a valid IPv4 address, a valid IPv6 address, or neither.  In order to solve this, we can first count the delimiters in the string.  If there are three periods in the address, we will try invalidating it as an IPv4 address and return "IPv4" if we couldn't.  If there are seven colons, we will do the same thing but as an IPv6 address.  If there are neither, we will return "neither."

To validate the addresses, we will just list conditions that would invalidate them and if they don't fail any of those conditions, they are valid.

First, let's set up the paths to direct the IP to.

If the IP has three periods, we will see if it is a valid IPv4 address.  

If it is, we will return "IPv4".

If it is not, we will return neither because there'd be no way for it to be a valid IPv6 address either.

        if IP.count('.') == 3:
            if valid_IPV4(IP):
                return "IPv4"
            else:
                return "Neither"

 

Similarly, if the address has seven colons, we will see if it is a valid IPv6 address.

        if IP.count(":") == 7:
            if valid_IPV6(IP):
                return "IPv6"
            else:
                return "Neither"

 

If it has neither three periods nor seven colons, it is neither one of these two types of addresses.

        else:
            return "Neither"

Now that we have the pathways set, let's create the actual validation functions.

Let's start with IPv4.

        def valid_IPV4(IP:str) -> bool:

 

We can start by splitting each byte into its own component.

 172.16.254.1 will transform into [172,16,254,1]

            IP = IP.split(".")

 

Once we have a list of these number components, we can iterate through the list and run each component through tests that would invalidate it as a proper byte that would be in an IPv4 address.

            for num in IP:

 

If the byte is empty, not zero, but empty, that would be invalid.

                if not num:
                    return False

 

If there is a leading zero to another value, that would be invalid.

                if len(num) > 1 and num[0] == "0":
                    return False

 

If any of the digits aren't actually digits, that would be invalid.

                for digit in num:
                    if not digit.isdigit():
                        return False

 

If the component falls outside the bounds of [0,255] then it is negative, which is invalid, or contains more than eight bits, which is also invalid.

                if int(num) < 0 or int(num) > 255:
                    return False

 

If none of these tests failed, we have validated the IPv4 address so we will return true.

            return True

Next, we will make the IPv6 validation function.

The idea is going to be the same, but with different invalidation tests.

        def valid_IPV6(IP:str) -> bool:

 

In an IPv6 address, we can have hexadecimal numbers.  So let's make a list of valid numbers we would expect to see in the address.

            hexadecimals = '0123456789abcdefABCDEF'

 

Same as before, let's split each address into components.

"2001:0db8:85a3:0:0:8A2E:0370:7334" will transform into [2001, 0db8, 85a3, 0, 0, 8A2E, 0370, 7334]

            IP = IP.split(":")

 

Once we have a list of these number components, we can iterate through the list and run each component through tests that would invalidate it as a proper value that would be in an IPv4 address.

            for num in IP:

 

If the number is empty, that is invalid.  

If the number's length is greater than four, that falls outside the bounds of the sixteen-bit component.

                if len(num) == 0 or len(num) > 4:
                    return False

 

For each character in the component, if that character isn't in the list of appropriate hexadecimals, that is invalid.

                for char in num:
                    if char not in hexadecimals:
                        return False

 

If none of these tests failed, we have validated the IPv6 address so we will return true.

            return True