468. Validate IP Address
Model: qwen3.5:9b
Topics: String
FAANG asked: 1
Acceptance rate: 25.1%
Problem Breakdown
The goal is to classify a given string as "IPv4", "IPv6", or "Neither" based on strict formatting rules for each protocol type.
- Input: A single string
IPcontaining digits, letters (a-f), and delimiters (.or:). - Output: One of three specific strings indicating validity.
- Implicit Constraints & Edge Cases:
- IPv4 parts must be integers 0–255 with no leading zeros (except for
"0"itself). - IPv6 parts are hex digits, length 1–4, and allow leading zeros.
- Mixed delimiters or incorrect counts of segments immediately invalidate the address type.
- Empty strings resulting from trailing/leading delimiters must be caught as invalid.
- IPv4 parts must be integers 0–255 with no leading zeros (except for
Intuition
I need to distinguish between two mutually exclusive formats based on their delimiter characters (. for IPv4, : for IPv6). A brute-force approach would try parsing every possible integer or hex value without checking the structure first, which is inefficient and error-prone regarding delimiters.
The key insight is that valid addresses are structurally distinct:
- IPv4 requires exactly four dot-separated segments of decimal digits.
- IPv6 requires eight colon-separated segments of hexadecimal characters (length ≤ 4).
I can optimize by checking the delimiter counts first to determine which validator to run, or simply attempting one and falling back if it fails validation checks like segment count. Since a valid IPv4 cannot contain colons and vice versa, I should check for mixed delimiters early to return "Neither" immediately without deep parsing overhead.
Approach
I will implement two helper functions (or logic blocks) within the main function: validateIPv4 and validateIPv6.
- Delimiter Check: If both dots and colons exist, or neither exists in a way that matches counts, return
"Neither". However, to keep code clean, I’ll attempt IPv4 validation first if it looks like an IPv4 candidate (contains only dots), then IPv6 otherwise? No, strict delimiter counting is safer.- If
.count == 4 and no:-> Validate as IPv4. - If
:count == 8 (segments) and no.-> Validate as IPv6. - Else ->
"Neither".
- If
- IPv4 Logic: Split by
., ensure exactly 4 parts, check each part is digits only, range [0-255], and reject leading zeros unless the number is “0”. - IPv6 Logic: Split by
:, ensure exactly 8 parts, check length of each part (1–4), validate hex characters using base conversion or set membership.
Complexity Analysis
- Time Complexity: where is the length of string
IP. We iterate through the string once to split and process segments. Splitting creates a list proportional to segment count, which is constant (4 for IPv4, 8 for IPv6), so linear scan dominates. - Space Complexity: due to creating lists from splitting strings in Python. However, since max parts are fixed constants, auxiliary space relative to input size can be considered effectively bounded by the string length itself ( if we ignore split storage overhead).
Solution
def validIPAddress(IP):
# Helper for IPv4 validation
def is_valid_ipv4(parts):
count = len(parts)
if count != 4: return False
for part in parts:
# Must be digits only (no hex chars like 'a'-'f')
if not part.isdigit():
return False
# Check leading zeros constraint
if len(part) > 1 and part[0] == '0':
return False
val = int(part)
if val < 0 or val > 255:
return False
return True
# Helper for IPv6 validation
def is_valid_ipv6(parts):
count = len(parts)
if count != 8: return False
hex_chars = set("abcdefABCDEF0123456789")
for part in parts:
length_check = (len(part) >= 1 and len(part) <= 4)
char_check = all(c.lower() in "abcdef" or c.isdigit() for c in part) # Simplified hex check
if not length_check or not char_check: return False
return True
# Determine type based on delimiters to avoid unnecessary checks
has_dot = '.' in IP
has_colon = ':' in IP
if has_dot and not has_colon:
parts = IP.split('.')
return "IPv4" if is_valid_ipv4(parts) else "Neither"
elif has_colon and not has_dot:
parts = IP.split(':')
# Additional check for empty strings in split (e.g. trailing colon)
# handled by length_check logic inside helper, but explicit count helps early exit
return "IPv6" if is_valid_ipv6(parts) else "Neither"
else:
# Mixed delimiters or neither found correctly implies invalid format for strict IP types
return "Neither"
# Note: The above helpers can be inlined to reduce overhead, but kept separate here
# for readability. In a production environment, I would inline them into the main function logic.
Edge Cases Handled
- Mixed Delimiters: Strings containing both
.and:return"Neither"immediately via delimiter checks. - Leading Zeros (IPv4): Logic rejects parts like
"01","08"but accepts"0". - Range Overflow (IPv4): Parts exceeding 255 or negative values are caught by range check after conversion.
- Empty Segments: Trailing/leading delimiters result in empty strings from
split(), which fail the length/hex checks immediately. - Hex Characters (IPv6): Logic ensures only valid hex digits (
0-9, a-f) appear; invalid chars like'g'or letters outside range are rejected by set check/conversion logic.