468. Validate IP Address

MediumString

Problem Description

The task is to verify the validity of an input string queryIP that is supposed to represent an IP address. The program should identify whether the IP address is a valid IPv4 address, a valid IPv6 address, or neither.

A valid IPv4 address is defined by four decimal number segments separated by dots ('.'). Each segment must be within the range of 0 to 255, inclusive, and may not have leading zeros. For instance, "192.168.1.1" is valid, whereas "192.168.01.1" is not.

A valid IPv6 address consists of eight hexadecimal number segments separated by colons (':'). Each segment must have a length of at least 1 and a maximum of 4 characters, and can contain digits, as well as lowercase or uppercase letters 'a' to 'f'. Leading zeros are allowed in IPv6 segments. An example of a valid IPv6 address is "2001:0db8:85a3:0000:0000:8a2e:0370:7334".

The output should be either "IPv4", "IPv6", or "Neither" based on whether the input string matches the criteria for being a valid IPv4 address, valid IPv6 address, or doesn't match the criteria for either, respectively.

Intuition

To solve this problem, the solution must differentiate between the potential formats of IPv4 and IPv6, which is done by checking whether the input string contains dots (suggesting an IPv4) or colons (suggesting an IPv6).

For IPv4, we need to:

Split the string by dots and ensure that there are exactly four segments.
Check if each segment is a number (digit only).
Verify that each segment is within the 0-255 range.
Make sure there are no leading zeros except for the single digit zero.

For IPv6, we need to:

Split the string by colons and ensure that there are exactly eight segments.
Verify that each segment has between 1 and 4 characters.
Check if each character in every segment is a valid hexadecimal digit (0-9, a-f, A-F).

If any of these checks fail, the output should be "Neither". Otherwise, the appropriate format name is returned. The provided solution follows these steps exactly to determine the input string's format.

Solution Approach

The implementation follows a straightforward approach using string operations and validation checks. Here's a detailed walkthrough of the algorithm based on the provided solution:

The first step is to check if the input string IP contains a dot .. If it does, the algorithm proceeds to check if it is a valid IPv4 address.

a. The string is split into 'segments' using the split method. This creates a list where each element corresponds to a segment of the potential IPv4 address.

b. After splitting, we check if we have exactly 4 segments. If not, we return "Neither" because an IPv4 address should contain exactly four parts.

c. We then iterate over each segment to perform several checks: - Use .isdigit() to confirm if the segment consists only of digit characters. - Convert the segment to an integer and check if it is between 0 and 255 (the valid range for IPv4 segments). - Ensure that the segment does not contain any leading zeros unless it is the single digit zero (e.g., "0" is valid, but "01" is not).

d. If all segments pass the checks, we return "IPv4". If any segment fails a check, we immediately return "Neither".
If the input string does not contain a dot . but contains a colon :, the algorithm proceeds to check if it might be a valid IPv6 address.

a. A similar split operation is performed, but this time using the colon as the delimiter.

b. We check for exactly 8 segments because this is what a standard IPv6 format requires.

c. We go through each segment and perform the following checks: - Confirm that segment is not empty and its length does not exceed 4 characters. - Use a loop to check if every character in the segment is a valid hexadecimal digit. This check is done using the fact that string.hexdigits in Python contains all valid hexadecimal characters (0-9, a-f, A-F).

d. As with IPv4, if all segments of the IPv6 address are valid, we return "IPv6". If any segment is invalid, we return "Neither".
If the input string neither contains a dot nor a colon, it can't be a valid IP of either type, so we return "Neither".

This algorithm does not require any sophisticated data structures or patterns. It relies on string methods and control structures (loops and conditionals) to apply the validation logic. The solution is efficient with a time complexity of O(1). This is because, regardless of the length of the input string, there will always be a fixed number of segments to process (either 4 for IPv4 or 8 for IPv6), so the number of operations does not scale with the size of the input.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Say we have the input string queryIP = "192.168.1.1", and we need to determine if it's a valid IPv4 or IPv6 address, or neither.

Check for the presence of a dot (.). Since the string contains dots, we consider it as a potential IPv4 address candidate.

a. Split the queryIP by dots. The split method gives us the list ["192", "168", "1", "1"].

b. Verify that the split list has exactly four segments, which it does in this case (192, 168, 1, 1).

c. Perform validation for each segment: - Check if each is numeric using .isdigit(). All segments here are numeric. - Convert each segment to an integer and check if it falls within the 0-255 range. The segments 192, 168, 1, and 1 are all within this valid range. - Ensure no leading zeros. In this example, no segment has leading zeros.

d. Since all checks for IPv4 are passed, return "IPv4".

If instead the queryIP was "2001:0db8:85a3:0000:0000:8a2e:0370:7334", we would start by checking for the presence of colons (:):

Since the string contains colons, we evaluate it as a potential IPv6 address.

a. Split the queryIP by colons, resulting in ["2001", "0db8", "85a3", "0000", "0000", "8a2e", "0370", "7334"].

b. Make sure there are exactly eight segments, which there are.

c. Validate each segment: - Check the segment length to make sure it's between 1 and 4 characters, which all of the listed segments comply with. - Verify each character of every segment is a valid hexadecimal digit. Each character in our segments is a valid hexadecimal character.

d. All checks for IPv6 are passed, so we would return "IPv6".

In either case, if the string fails to meet the conditions for both IPv4 and IPv6, we would return "Neither". For example, queryIP = "256.256.256.256" fails the IPv4 range check, and queryIP = "2001:db8:85a3::8a2e:37023:7334" fails because it has more than 4 characters in a segment and doesn't have exactly eight segments for an IPv6, so the return would be "Neither".

Solution Implementation

1class Solution:
2    def validIPAddress(self, IP: str) -> str:
3        """
4        Validates whether the given IP address is a valid IPv4 or IPv6 address.
5      
6        :param IP: A string containing the IP address to validate.
7        :return: A string either "IPv4", "IPv6" or "Neither", denoting the type of IP address.
8        """
9        if "." in IP:
10            return self.validate_ipv4(IP)
11        elif ":" in IP:
12            return self.validate_ipv6(IP)
13        else:
14            return "Neither"
15  
16    def validate_ipv4(self, ip: str) -> str:
17        """
18        Validates IPv4 addresses.
19
20        :param ip: A string of the IPv4 address to validate.
21        :return: "IPv4" if valid, otherwise "Neither".
22        """
23        segments = ip.split(".")
24        if len(segments) != 4:
25            return "Neither"
26      
27        for segment in segments:
28            # Check if the segment is a number between 0 and 255
29            # and does not have leading zeros
30            if not segment.isdigit() or not 0 <= int(segment) <= 255 or (segment[0] == "0" and len(segment) > 1):
31                return "Neither"
32      
33        return "IPv4"
34  
35    def validate_ipv6(self, ip: str) -> str:
36        """
37        Validates IPv6 addresses.
38
39        :param ip: A string of the IPv6 address to validate.
40        :return: "IPv6" if valid, otherwise "Neither".
41        """
42        segments = ip.split(":")
43        if len(segments) != 8:
44            return "Neither"
45
46        for segment in segments:
47            # Check if the segment is empty, longer than 4 characters or
48            # contains characters which are not hexadecimal digits
49            if not segment or len(segment) > 4 or not all(c in '0123456789abcdefABCDEF' for c in segment):
50                return "Neither"
51
52        return "IPv6"
53

1public class Solution {
2    // Method to validate IP address
3    public String validIPAddress(String queryIP) {
4        // Helper function to validate IPv4 addresses
5        boolean isIPv4() {
6            // Split the input string by '.', IPv4 should have 4 parts
7            String[] octets = queryIP.split("\\.");
8            // Check if there are exactly 4 octets
9            if (octets.length != 4) {
10                return false;
11            }
12            // Validate each octet
13            for (String octet : octets) {
14                // Convert string to a number
15                int num;
16                try {
17                    num = Integer.parseInt(octet);
18                } catch (NumberFormatException e) {
19                    return false;
20                }
21                // Check if the octet is within the valid range and has no leading zeros unless it's '0'
22                if (num < 0 || num > 255 || !String.valueOf(num).equals(octet) || (octet.length() > 1 && octet.startsWith("0"))) {
23                    return false;
24                }
25            }
26            // If all octets are valid, return true
27            return true;
28        }
29
30        // Helper function to validate IPv6 addresses
31        boolean isIPv6() {
32            // Split the input string by ':', IPv6 should have 8 parts
33            String[] blocks = queryIP.split(":");
34            // Check if there are exactly 8 blocks
35            if (blocks.length != 8) {
36                return false;
37            }
38            // Validate each block
39            for (String block : blocks) {
40                // Check block length is between 1 and 4 characters
41                if (block.length() == 0 || block.length() > 4) {
42                    return false;
43                }
44                // Check if each character in the block is a valid hexadecimal digit
45                for (char c : block.toCharArray()) {
46                    if (!Character.toString(c).matches("[0-9a-fA-F]")) {
47                        return false;
48                    }
49                }
50            }
51            // If all blocks are valid, return true
52            return true;
53        }
54
55        // Determine the IP address type
56        if (queryIP.contains(".")) {  // Likely an IPv4 address
57            if (isIPv4()) {
58                return "IPv4";
59            }
60        } else if (queryIP.contains(":")) {  // Likely an IPv6 address
61            if (isIPv6()) {
62                return "IPv6";
63            }
64        }
65        // If neither, return 'Neither'
66        return "Neither";
67    }
68}
69
70// Note: To use these helper functions within the validIPAddress method, you may want to make them static methods of the Solution class, or alternatively, you could define them outside the validIPAddress method (inside the Solution class) and call them as needed.
71

1#include <string>
2#include <vector>
3#include <sstream>
4
5class Solution {
6public:
7    std::string validIPAddress(std::string queryIP) {
8        // Helper function to validate IPv4 addresses
9        auto isIPv4 = [&]() -> bool {
10            std::istringstream ss(queryIP);
11            std::string octet;
12            int count = 0;
13
14            while (getline(ss, octet, '.')) {
15                // IPv4 should have exactly 4 octets
16                if (++count > 4) return false;
17
18                // Validate each octet
19                if (octet.empty() || octet.size() > 3 || (octet.size() > 1 && octet[0] == '0')) return false;
20                for (char c : octet) {
21                    if (!isdigit(c)) return false;
22                }
23
24                // Convert string to a number and check it is in the range [0, 255]
25                int num = std::stoi(octet);
26                if (num < 0 || num > 255) return false;
27            }
28
29            // Check we have exactly 4 octets
30            return count == 4 && ss.eof();
31        };
32
33        // Helper function to validate IPv6 addresses
34        auto isIPv6 = [&]() -> bool {
35            std::istringstream ss(queryIP);
36            std::string block;
37            int count = 0;
38
39            while (getline(ss, block, ':')) {
40                // IPv6 should have exactly 8 blocks
41                if (++count > 8) return false;
42
43                // Validate each block
44                if (block.empty() || block.size() > 4) return false;
45                for (char c : block) {
46                    if (!isxdigit(c)) return false;
47                }
48            }
49
50            // Check we have exactly 8 blocks
51            return count == 8 && ss.eof();
52        };
53
54        // Determine the type of IP address and return the corresponding result
55        if (isIPv4()) {
56            return "IPv4";
57        } else if (isIPv6()) {
58            return "IPv6";
59        } else {
60            return "Neither";
61        }
62    }
63};
64

1function validIPAddress(queryIP: string): string {
2    // Helper function to validate IPv4 addresses
3    const isIPv4 = (): boolean => {
4        // Split the input string by '.', IPv4 should have 4 parts
5        const octets = queryIP.split('.');
6        // Check if there are exactly 4 octets
7        if (octets.length !== 4) {
8            return false;
9        }
10        // Validate each octet
11        for (const octet of octets) {
12            // Convert string to a number
13            const num = Number(octet);
14            // Check if the octet is within the valid range and is a valid string representation of the number
15            // Leading zeros are not allowed in IPv4 octets.
16            if (num < 0 || num > 255 || String(num) !== octet || /^0[0-9]/.test(octet)) {
17                return false;
18            }
19        }
20        // If all octets are valid, return true
21        return true;
22    };
23
24    // Helper function to validate IPv6 addresses
25    const isIPv6 = (): boolean => {
26        // Split the input string by ':', IPv6 should have 8 parts
27        const blocks = queryIP.split(':');
28        // Check if there are exactly 8 blocks
29        if (blocks.length !== 8) {
30            return false;
31        }
32        // Validate each block
33        for (const block of blocks) {
34            // Check block length is between 1 and 4
35            if (block.length === 0 || block.length > 4) {
36                return false;
37            }
38            // Check each character in the block
39            for (const char of block) {
40                // Check if the character is a valid hexadecimal number
41                if (!(/[0-9a-fA-F]/.test(char))) {
42                    return false;
43                }
44            }
45        }
46        // If all blocks are valid, return true
47        return true;
48    };
49
50    // Determine the type of IP address
51    if (isIPv4()) {
52        return 'IPv4';
53    } else if (isIPv6()) {
54        return 'IPv6';
55    } else {
56        return 'Neither';
57    }
58}
59

Time and Space Complexity

The given python code determines whether a given string is a valid IPv4 or IPv6 address or neither. The analysis of the time and space complexity of the code is as follows:

Time Complexity:

The time complexity of the code is dependent on the number of segments and the length of the individual segments in the input IP address string.

For IPv4 validation, the code splits the string at periods (".") and checks if there are exactly four segments. Each segment must contain only digits, be in the range 0 to 255, and must not have leading zeroes unless it is just "0". The validation for each segment runs in O(1) time since there is a constant bound on the size of each segment (maximum three characters). Thus, the time complexity is O(1) for IPv4 addresses.
For IPv6 validation, the code splits the string at colons (":") and checks if there are exactly eight segments. Each segment must contain no more than four hexadecimal characters. Checking if a character is a hexadecimal digit has O(1) complexity because it checks against a finite set. Given that an IPv6 segment has at most four characters, checking all segments is O(1) as well. Thus, the time complexity is O(1) for IPv6 addresses.

Since the number of operations for both IPv4 and IPv6 address validations is bounded by a constant, the overall time complexity of the function is O(1). Note that string operations such as split have linear time complexity in the number of characters, but since the maximum length of an IP address is fixed and small, for the purposes of this problem, we can consider it to be O(1).

Space Complexity:

The space complexity is mainly determined by the space needed to store the segments after splitting the initial string and any minimal extra space for iteration and validation.
In the worst case, IPv4 addresses will have four segments, and IPv6 addresses will have eight segments. The space required to store these segments is O(1) since the number of segments and the maximum size of each segment is constant and does not grow with the input size.
There is no other significant additional space used in the algorithm since the checks for each segment are done in-place, and no extra data structures are created that depend on the input size.

Hence, the space complexity of the code is also O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know