Validate IP Address

Medium Arrays & Hashing Simulation Original on LeetCode

Reported atMeta

Validate IP Address is a medium arrays & hashing problem solved with the simulation pattern. The best approach, optimal (count separators, split and check each part), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (regular expressions) up.

Problem

Given a string queryIP, return "IPv4" if it is a valid IPv4 address, "IPv6" if it is a valid IPv6 address, and "Neither" otherwise.

A valid IPv4 address has four decimal parts separated by dots. Each part is a number from 0 to 255 written without leading zeros, so "7" and "0" are fine but "07" and "256" are not.

A valid IPv6 address has eight groups separated by colons. Each group has one to four hexadecimal characters (0–9, a–f, A–F); leading zeros are allowed, but a group may not be empty, so shortened forms like "::" are invalid.

Examples

Example 1

Input
queryIP = "192.168.0.10"
Output
"IPv4"
Why
Four decimal parts, each between 0 and 255 and without extra leading zeros.

Example 2

Input
queryIP = "fe80:0:0:0:204:61ff:fe9d:f156"
Output
"IPv6"
Why
Eight groups of one to four hexadecimal digits separated by colons.

Example 3

Input
queryIP = "10.01.2.3"
Output
"Neither"
Why
The part "01" has a leading zero, which IPv4 does not allow.

Constraints

  • 1 <= queryIP.length <= 100
  • queryIP contains only English letters, digits, '.' and ':'.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 25 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (regular expressions)O(n)O(1)
Optimal (count separators, split and check each part)O(n)O(n)

1Brute force (regular expressions)

TimeO(n)Both patterns are fixed-size and match in time linear in the string length (building the pattern is a constant cost, though not a small one).
SpaceO(1)The compiled patterns have constant size.

Describe each format with a regular expression and test the whole string against both. An IPv4 part is one of 25[0-5], 2[0-4]d, 1dd, [1-9]d or a single digit, which encodes both the 0–255 range and the no-leading-zero rule. An IPv6 group is one to four hex characters. The regex engine does the parsing, at the cost of building and running a general matcher.

  1. part = (25[0-5]|2[0-4][0-9]|1[0-9][0-9]|[1-9][0-9]|[0-9]); IPv4 = (part.){3}part.
  2. group = [0-9a-fA-F]{1,4}; IPv6 = (group:){7}group.
  3. Return "IPv4" or "IPv6" for a full match, else "Neither".
class Solution {
    private static final String PART = "(25[0-5]|2[0-4][0-9]|1[0-9][0-9]|[1-9][0-9]|[0-9])";
    private static final java.util.regex.Pattern V4 = java.util.regex.Pattern.compile("(" + PART + "\\.){3}" + PART);
    private static final java.util.regex.Pattern V6 = java.util.regex.Pattern.compile("([0-9a-fA-F]{1,4}:){7}[0-9a-fA-F]{1,4}");

    public String validIPAddress(String queryIP) {
        if (V4.matcher(queryIP).matches()) return "IPv4";
        if (V6.matcher(queryIP).matches()) return "IPv6";
        return "Neither";
    }
}

2Optimal (count separators, split and check each part)

TimeO(n)One pass to count separators, one to split, and each piece is checked character by character.
SpaceO(n)The split pieces together hold the n characters of the input.

Count the dots and colons first. Exactly three dots and no colons means only IPv4 is possible; exactly seven colons and no dots means only IPv6 is possible. Split on that separator while keeping empty pieces, then check every piece with simple character rules. Each character is looked at a constant number of times and no regex engine is needed.

  1. Count '.' and ':'. If dots == 3 and colons == 0, check IPv4; if colons == 7 and dots == 0, check IPv6; otherwise return "Neither".
  2. IPv4 piece: length 1–3, all digits, not starting with '0' when longer than 1, numeric value ≤ 255.
  3. IPv6 piece: length 1–4, each character in 0–9, a–f or A–F.
  4. Return the format if every piece passes, else "Neither".
class Solution {
    public String validIPAddress(String queryIP) {
        int dots = 0, colons = 0;
        for (char c : queryIP.toCharArray()) {
            if (c == '.') dots++;
            else if (c == ':') colons++;
        }
        if (dots == 3 && colons == 0) return isV4(queryIP) ? "IPv4" : "Neither";
        if (colons == 7 && dots == 0) return isV6(queryIP) ? "IPv6" : "Neither";
        return "Neither";
    }

    private boolean isV4(String ip) {
        for (String part : ip.split("\\.", -1)) {
            if (part.isEmpty() || part.length() > 3) return false;
            if (part.length() > 1 && part.charAt(0) == '0') return false;
            int value = 0;
            for (char c : part.toCharArray()) {
                if (c < '0' || c > '9') return false;
                value = value * 10 + (c - '0');
            }
            if (value > 255) return false;
        }
        return true;
    }

    private boolean isV6(String ip) {
        for (String part : ip.split(":", -1)) {
            if (part.isEmpty() || part.length() > 4) return false;
            for (char c : part.toCharArray()) {
                boolean hex = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F');
                if (!hex) return false;
            }
        }
        return true;
    }
}

Edge cases to test

  • Leading zeros in an IPv4 part ("01" is invalid, "0" is fine)
  • IPv4 part above 255, or with more than three digits
  • Empty parts from consecutive, leading or trailing separators ("1..2.3", "1.2.3.4.", "::" compression)
  • IPv6 group with five characters or a letter outside a–f / A–F
  • Mixed separators, or the wrong number of parts

Hints

Hint 1

Decide which format to test by looking at the separators: exactly three dots means IPv4 is possible, exactly seven colons means IPv6 is possible, anything else is neither.

Hint 2

Split on the separator but keep empty pieces, so "1.2..3" is rejected instead of silently skipping the empty part.

Hint 3

IPv4 part: 1–3 digits, no leading zero unless the part is exactly "0", value ≤ 255. IPv6 group: 1–4 characters, each a digit or a letter a–f in either case.

FAQ

What is the best time complexity for Validate IP Address?

Optimal (count separators, split and check each part) runs in O(n) time and O(n) extra space. One pass to count separators, one to split, and each piece is checked character by character.

Which pattern does Validate IP Address use?

It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).

Is there a brute force solution for Validate IP Address?

Yes. Brute force (regular expressions) takes O(n) time and O(1) space. Describe each format with a regular expression and test the whole string against both.

Which edge cases should I test for Validate IP Address?

Leading zeros in an IPv4 part ("01" is invalid, "0" is fine); IPv4 part above 255, or with more than three digits; Empty parts from consecutive, leading or trailing separators ("1..2.3", "1.2.3.4.", "::" compression); IPv6 group with five characters or a letter outside a–f / A–F; Mixed separators, or the wrong number of parts.