LeetCode 468 - Validate IP Address

The problem asks us to determine whether a given string represents a valid IPv4 address, a valid IPv6 address, or neither.

leetcodemediumstring

LeetCode Problem 468

Difficulty: 🟡 Medium
Topics: String

Solution

Problem Understanding

The problem asks us to determine whether a given string represents a valid IPv4 address, a valid IPv6 address, or neither. We are given a single string called queryIP, and we must return one of three exact strings:

  • "IPv4" if the input is a valid IPv4 address
  • "IPv6" if the input is a valid IPv6 address
  • "Neither" if the input does not satisfy either format

An IPv4 address consists of exactly four decimal numbers separated by dots (.). Each number must satisfy several strict rules:

  • The value must be between 0 and 255
  • The segment cannot be empty
  • Leading zeros are not allowed unless the segment itself is exactly "0"

For example:

  • "192.168.1.1" is valid
  • "01.2.3.4" is invalid because "01" has a leading zero
  • "256.1.1.1" is invalid because 256 > 255

An IPv6 address consists of exactly eight hexadecimal groups separated by colons (:). Each group:

  • Must contain between 1 and 4 characters
  • May contain digits 0-9
  • May contain lowercase letters a-f
  • May contain uppercase letters A-F
  • May contain leading zeros

For example:

  • "2001:0db8:85a3:0:0:8A2E:0370:7334" is valid
  • "02001:db8:85a3:0:0:8A2E:0370:7334" is invalid because one group has length 5
  • "2001:db8:85a3::8A2E:037j:7334" is invalid because j is not hexadecimal

The constraints are relatively small because the input is just a single string. This means runtime efficiency is not difficult to achieve, but correctness is critical because many edge cases exist.

Several edge cases can easily break a naive implementation:

  • Empty segments caused by consecutive separators such as "1..1.1" or "2001::1"
  • Trailing separators such as "1.1.1.1."
  • Leading zeros in IPv4 such as "192.168.01.1"
  • Invalid hexadecimal characters in IPv6
  • Incorrect number of segments
  • Mixing separators, such as dots and colons together

The problem guarantees that the string contains only letters, digits, '.', and ':', so we do not need to worry about other special characters.

Approaches

A brute-force approach would attempt to parse the string as every possible IP format using many ad hoc checks and repeated conversions. For example, we could try every partitioning possibility, validate numeric ranges repeatedly, and manually reconstruct the address. While this would eventually produce the correct answer, it would be unnecessarily complicated and error-prone. It also introduces redundant work because the format rules already clearly define how the string should be segmented.

The key insight is that both IPv4 and IPv6 have rigid structural rules. Instead of trying arbitrary parsing strategies, we can directly validate the structure based on the separator:

  • If the string contains dots, attempt IPv4 validation
  • If the string contains colons, attempt IPv6 validation
  • Otherwise, immediately return "Neither"

For IPv4, splitting by . must produce exactly four parts. Each part must be checked for:

  • Non-empty
  • Digits only
  • No leading zeros unless length is 1
  • Numeric value within [0, 255]

For IPv6, splitting by : must produce exactly eight parts. Each part must be checked for:

  • Length between 1 and 4
  • All characters are valid hexadecimal digits

Because the input size is tiny and each character is examined at most a constant number of times, this approach is both simple and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeated parsing and reconstruction attempts
Optimal O(n) O(n) Single pass validation after splitting

Algorithm Walkthrough

  1. First, determine which format the string may represent.

If the string contains a dot (.), it could be IPv4. If it contains a colon (:), it could be IPv6. If it contains neither or mixes formats incorrectly, it cannot be valid. 2. For IPv4 validation, split the string using ..

A valid IPv4 address must produce exactly four segments. If the split result does not contain four parts, return "Neither" immediately. 3. Validate each IPv4 segment individually.

For every segment:

  • Ensure it is not empty
  • Ensure every character is a digit
  • Reject leading zeros when length is greater than 1
  • Convert the segment to an integer and ensure it lies between 0 and 255

If any segment fails, the address is invalid. 4. If all IPv4 segments pass validation, return "IPv4".

At this point, every structural and numeric requirement has been satisfied. 5. For IPv6 validation, split the string using :.

A valid IPv6 address must produce exactly eight groups. Any other count immediately invalidates the address. 6. Validate each IPv6 group.

For every group:

  • Ensure its length is between 1 and 4
  • Ensure every character belongs to the hexadecimal set:

0123456789abcdefABCDEF

Leading zeros are allowed, so no special handling is needed. 7. If all IPv6 groups pass validation, return "IPv6". 8. If neither validator succeeds, return "Neither".

Why it works

The algorithm works because both IP formats are defined entirely by strict structural rules. IPv4 requires exactly four decimal segments with restricted numeric ranges and no leading zeros. IPv6 requires exactly eight hexadecimal groups with limited length. By checking every rule directly and rejecting immediately on violation, the algorithm guarantees that only correctly formatted addresses are accepted.

Python Solution

class Solution:
    def validIPAddress(self, queryIP: str) -> str:
        
        def is_ipv4(ip: str) -> bool:
            parts = ip.split(".")
            
            if len(parts) != 4:
                return False
            
            for part in parts:
                if len(part) == 0:
                    return False
                
                if not part.isdigit():
                    return False
                
                if len(part) > 1 and part[0] == "0":
                    return False
                
                value = int(part)
                
                if value < 0 or value > 255:
                    return False
            
            return True
        
        def is_ipv6(ip: str) -> bool:
            hex_chars = set("0123456789abcdefABCDEF")
            
            parts = ip.split(":")
            
            if len(parts) != 8:
                return False
            
            for part in parts:
                if len(part) == 0 or len(part) > 4:
                    return False
                
                for char in part:
                    if char not in hex_chars:
                        return False
            
            return True
        
        if "." in queryIP and is_ipv4(queryIP):
            return "IPv4"
        
        if ":" in queryIP and is_ipv6(queryIP):
            return "IPv6"
        
        return "Neither"

The implementation is divided into two helper functions, one for IPv4 validation and one for IPv6 validation. This separation keeps the logic clean and mirrors the problem statement directly.

The is_ipv4 function first splits the string into four parts. It validates the segment count before examining each segment individually. Each segment must be non-empty, contain only digits, avoid leading zeros, and stay within the numeric range [0, 255].

The is_ipv6 function similarly splits the string into eight groups. Each group must have length between 1 and 4 and consist entirely of hexadecimal characters.

The main method then checks whether the string resembles IPv4 or IPv6 and calls the corresponding validator. If neither validation succeeds, the function returns "Neither".

Go Solution

package main

import (
	"strconv"
	"strings"
)

func validIPAddress(queryIP string) string {

	isIPv4 := func(ip string) bool {
		parts := strings.Split(ip, ".")

		if len(parts) != 4 {
			return false
		}

		for _, part := range parts {

			if len(part) == 0 {
				return false
			}

			if len(part) > 1 && part[0] == '0' {
				return false
			}

			for _, ch := range part {
				if ch < '0' || ch > '9' {
					return false
				}
			}

			value, err := strconv.Atoi(part)

			if err != nil || value < 0 || value > 255 {
				return false
			}
		}

		return true
	}

	isIPv6 := func(ip string) bool {
		parts := strings.Split(ip, ":")

		if len(parts) != 8 {
			return false
		}

		for _, part := range parts {

			if len(part) == 0 || len(part) > 4 {
				return false
			}

			for _, ch := range part {
				isDigit := ch >= '0' && ch <= '9'
				isLower := ch >= 'a' && ch <= 'f'
				isUpper := ch >= 'A' && ch <= 'F'

				if !isDigit && !isLower && !isUpper {
					return false
				}
			}
		}

		return true
	}

	if strings.Contains(queryIP, ".") && isIPv4(queryIP) {
		return "IPv4"
	}

	if strings.Contains(queryIP, ":") && isIPv6(queryIP) {
		return "IPv6"
	}

	return "Neither"
}

The Go implementation follows the same overall structure as the Python version, but there are a few language-specific details.

Go does not have a built-in isdigit() method, so digit validation is performed manually using character comparisons. Similarly, hexadecimal validation uses explicit range checks for digits and uppercase or lowercase letters.

Integer conversion is handled using strconv.Atoi, which returns both the parsed integer and an error value. This makes invalid numeric parsing easy to detect safely.

Slices returned by strings.Split behave similarly to Python lists, so the segmentation logic remains straightforward.

Worked Examples

Example 1

Input:

"172.16.254.1"

The algorithm detects dots, so it attempts IPv4 validation.

After splitting:

Segment Index Segment
0 "172"
1 "16"
2 "254"
3 "1"

Validation process:

Segment Digits Only Leading Zero Check Numeric Value Valid
"172" Yes Pass 172 Yes
"16" Yes Pass 16 Yes
"254" Yes Pass 254 Yes
"1" Yes Pass 1 Yes

All segments pass, so the result is:

"IPv4"

Example 2

Input:

"2001:0db8:85a3:0:0:8A2E:0370:7334"

The algorithm detects colons, so it attempts IPv6 validation.

After splitting:

Group Index Group
0 "2001"
1 "0db8"
2 "85a3"
3 "0"
4 "0"
5 "8A2E"
6 "0370"
7 "7334"

Validation process:

Group Length Valid Hexadecimal Valid Valid
"2001" Yes Yes Yes
"0db8" Yes Yes Yes
"85a3" Yes Yes Yes
"0" Yes Yes Yes
"0" Yes Yes Yes
"8A2E" Yes Yes Yes
"0370" Yes Yes Yes
"7334" Yes Yes Yes

All groups pass, so the result is:

"IPv6"

Example 3

Input:

"256.256.256.256"

The algorithm attempts IPv4 validation.

After splitting:

Segment Numeric Value Valid Range
"256" 256 No
"256" 256 No
"256" 256 No
"256" 256 No

Since 256 > 255, validation fails immediately.

Result:

"Neither"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is examined at most a constant number of times
Space O(n) Splitting the string creates temporary arrays of segments

The runtime is linear in the length of the input string because validation scans each segment once. Splitting the string also requires linear processing. The extra space comes from storing the split components, which together contain all characters of the original input.

Test Cases

solution = Solution()

# Provided examples
assert solution.validIPAddress("172.16.254.1") == "IPv4"  # standard IPv4
assert solution.validIPAddress("2001:0db8:85a3:0:0:8A2E:0370:7334") == "IPv6"  # standard IPv6
assert solution.validIPAddress("256.256.256.256") == "Neither"  # IPv4 values out of range

# IPv4 edge cases
assert solution.validIPAddress("0.0.0.0") == "IPv4"  # minimum values
assert solution.validIPAddress("255.255.255.255") == "IPv4"  # maximum values
assert solution.validIPAddress("192.168.01.1") == "Neither"  # leading zero
assert solution.validIPAddress("1.1.1") == "Neither"  # too few segments
assert solution.validIPAddress("1.1.1.1.") == "Neither"  # trailing separator
assert solution.validIPAddress("1..1.1") == "Neither"  # empty segment
assert solution.validIPAddress("abc.def.gha.bcd") == "Neither"  # non-numeric
assert solution.validIPAddress("999.1.1.1") == "Neither"  # segment too large

# IPv6 edge cases
assert solution.validIPAddress("2001:db8:85a3:0:0:8A2E:0370:7334") == "IPv6"  # valid mixed case
assert solution.validIPAddress("2001:0db8:85a3::8A2E:0370:7334") == "Neither"  # empty group
assert solution.validIPAddress("02001:0db8:85a3:0000:0000:8a2e:0370:7334") == "Neither"  # group too long
assert solution.validIPAddress("2001:db8:85a3:0:0:8A2E:0370:zzzz") == "Neither"  # invalid hex chars
assert solution.validIPAddress("1:2:3:4:5:6:7") == "Neither"  # too few groups
assert solution.validIPAddress("1:2:3:4:5:6:7:8:9") == "Neither"  # too many groups

# Mixed invalid formats
assert solution.validIPAddress("1e1.4.5.6") == "Neither"  # invalid IPv4 characters
assert solution.validIPAddress("12..33.4") == "Neither"  # consecutive separators
assert solution.validIPAddress(":.") == "Neither"  # malformed input
Test Why
"172.16.254.1" Valid standard IPv4
"2001:0db8:85a3:0:0:8A2E:0370:7334" Valid standard IPv6
"256.256.256.256" IPv4 value exceeds allowed range
"0.0.0.0" Minimum IPv4 values
"255.255.255.255" Maximum IPv4 values
"192.168.01.1" Detects forbidden leading zeros
"1.1.1" Too few IPv4 segments
"1.1.1.1." Trailing separator creates empty segment
"1..1.1" Consecutive dots create empty segment
"abc.def.gha.bcd" Non-digit IPv4 input
"999.1.1.1" Numeric overflow in IPv4
"2001:db8:85a3:0:0:8A2E:0370:7334" Valid mixed-case hexadecimal
"2001:0db8:85a3::8A2E:0370:7334" Empty IPv6 group
"02001:0db8:85a3:0000:0000:8a2e:0370:7334" IPv6 group too long
"2001:db8:85a3:0:0:8A2E:0370:zzzz" Invalid hexadecimal characters
"1:2:3:4:5:6:7" Too few IPv6 groups
"1:2:3:4:5:6:7:8:9" Too many IPv6 groups
"1e1.4.5.6" Invalid IPv4 alphabetic character
"12..33.4" Empty IPv4 segment
":." Completely malformed format

Edge Cases

One important edge case is leading zeros in IPv4 segments. Many implementations incorrectly accept values like "192.168.01.1" because converting "01" to an integer produces 1, which is numerically valid. However, the problem explicitly forbids leading zeros unless the segment is exactly "0". The implementation handles this by checking whether the segment length exceeds 1 while beginning with '0'.

Another critical edge case is empty segments caused by consecutive separators or trailing separators. Inputs such as "1..1.1" or "1.1.1.1." produce empty strings after splitting. A naive parser might ignore these accidentally. The implementation explicitly checks for zero-length segments and rejects them immediately.

A third important edge case is invalid hexadecimal characters in IPv6 addresses. IPv6 groups may contain only digits and letters a-f or A-F. Inputs like "2001:db8:85a3:0:0:8A2E:0370:zzzz" look structurally correct but contain invalid characters. The implementation validates every character individually against the allowed hexadecimal set, ensuring correctness.

A final subtle edge case is incorrect segment counts. IPv4 must contain exactly four segments, while IPv6 must contain exactly eight groups. Inputs with too many or too few separators are invalid even if all individual pieces look correct. The implementation validates the segment count before doing any deeper checks, preventing malformed addresses from slipping through.