# LeetCode 468: Validate IP Address

## Problem Restatement

We are given a string `queryIP`.

We need to return one of three strings:

```python
"IPv4"
"IPv6"
"Neither"
```

Return `"IPv4"` if the string is a valid IPv4 address.

Return `"IPv6"` if the string is a valid IPv6 address.

Otherwise, return `"Neither"`.

A valid IPv4 address has four decimal parts separated by dots. Each part must be between `0` and `255`, and leading zeros are not allowed. A valid IPv6 address has eight hexadecimal parts separated by colons. Each part must have length from `1` to `4`, and leading zeros are allowed. The official problem asks us to classify `queryIP` as `"IPv4"`, `"IPv6"`, or `"Neither"`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `queryIP` |
| Output | `"IPv4"`, `"IPv6"`, or `"Neither"` |
| IPv4 separator | Dot `.` |
| IPv6 separator | Colon `:` |
| IPv4 parts | Exactly `4` |
| IPv6 parts | Exactly `8` |

Function shape:

```python
def validIPAddress(queryIP: str) -> str:
    ...
```

## Examples

Example 1:

```python
queryIP = "172.16.254.1"
```

It has four dot-separated parts:

```python
172
16
254
1
```

Each part is numeric, each value is between `0` and `255`, and there are no leading zeros.

Answer:

```python
"IPv4"
```

Example 2:

```python
queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
```

It has eight colon-separated parts.

Each part has length from `1` to `4`.

Each character is a valid hexadecimal character.

Answer:

```python
"IPv6"
```

Example 3:

```python
queryIP = "256.256.256.256"
```

Each part is numeric, but `256` is larger than `255`.

Answer:

```python
"Neither"
```

Example 4:

```python
queryIP = "192.168.01.1"
```

The part `"01"` has a leading zero.

Answer:

```python
"Neither"
```

## First Thought: Use Built-In IP Parsing

In real application code, we might use a standard library to parse IP addresses.

But in this problem, we need to implement the validation rules directly.

Also, the problem has exact rules:

| Type | Rule |
|---|---|
| IPv4 | Four decimal parts |
| IPv4 | No leading zeros unless the part is exactly `"0"` |
| IPv4 | Each value from `0` to `255` |
| IPv6 | Eight hexadecimal parts |
| IPv6 | Each part has length `1` to `4` |
| IPv6 | Leading zeros are allowed |

So the clean approach is to write two helpers:

```python
is_ipv4(queryIP)
is_ipv6(queryIP)
```

Then return the matching type.

## Key Insight

IPv4 and IPv6 have different separators.

An IPv4 candidate uses dots:

```python
.
```

An IPv6 candidate uses colons:

```python
:
```

So we can check based on which separator appears.

But we still must validate every segment carefully.

For IPv4:

```python
"172.16.254.1"
```

splits into:

```python
["172", "16", "254", "1"]
```

For IPv6:

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

splits into:

```python
["2001", "0db8", "85a3", "0", "0", "8A2E", "0370", "7334"]
```

The problem becomes segment validation.

## IPv4 Validation Rules

A valid IPv4 address must satisfy all of these:

| Rule | Example valid | Example invalid |
|---|---|---|
| Exactly 4 parts | `"1.2.3.4"` | `"1.2.3"` |
| Every part is non-empty | `"1.2.3.4"` | `"1..3.4"` |
| Every part contains only digits | `"172"` | `"17a"` |
| No leading zero if length > 1 | `"0"`, `"10"` | `"01"` |
| Value is between 0 and 255 | `"255"` | `"256"` |

## IPv6 Validation Rules

A valid IPv6 address must satisfy all of these:

| Rule | Example valid | Example invalid |
|---|---|---|
| Exactly 8 parts | Eight groups | Seven groups |
| Every part length is 1 to 4 | `"0"`, `"0db8"` | `""`, `"02001"` |
| Characters are hexadecimal | `"8A2E"` | `"037j"` |
| Leading zeros are allowed | `"0000"` | Not invalid |

The valid hexadecimal characters are:

```python
0123456789abcdefABCDEF
```

## Algorithm

Define `is_ipv4(ip)`.

1. Split by `"."`.
2. If there are not exactly `4` parts, return `False`.
3. For each part:
   1. If it is empty, return `False`.
   2. If it contains a non-digit character, return `False`.
   3. If it has length greater than `1` and starts with `"0"`, return `False`.
   4. If its integer value is greater than `255`, return `False`.
4. Return `True`.

Define `is_ipv6(ip)`.

1. Split by `":"`.
2. If there are not exactly `8` parts, return `False`.
3. For each part:
   1. If its length is less than `1` or greater than `4`, return `False`.
   2. If any character is not hexadecimal, return `False`.
4. Return `True`.

Then:

1. If `is_ipv4(queryIP)`, return `"IPv4"`.
2. If `is_ipv6(queryIP)`, return `"IPv6"`.
3. Return `"Neither"`.

## Correctness

The IPv4 helper checks exactly the IPv4 rules.

It requires exactly four parts, rejects empty parts, rejects non-digit characters, rejects leading zeros, and checks that each numeric value lies between `0` and `255`.

Therefore, it returns `True` exactly for valid IPv4 addresses.

The IPv6 helper checks exactly the IPv6 rules.

It requires exactly eight parts, checks that every part has length from `1` to `4`, and verifies that every character belongs to the hexadecimal character set.

Therefore, it returns `True` exactly for valid IPv6 addresses.

The main function returns `"IPv4"` if and only if the IPv4 helper accepts the input, `"IPv6"` if and only if the IPv6 helper accepts it, and `"Neither"` otherwise.

So the algorithm returns the required classification.

## Complexity

Let `n = len(queryIP)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each character is checked a constant number of times |
| Space | `O(n)` | Splitting creates segment lists |

The number of segments is bounded, but the split strings still depend on the input length.

## Implementation

```python
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 part == "":
                    return False

                if not part.isdigit():
                    return False

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

                if int(part) > 255:
                    return False

            return True

        def is_ipv6(ip: str) -> bool:
            parts = ip.split(":")

            if len(parts) != 8:
                return False

            valid = set("0123456789abcdefABCDEF")

            for part in parts:
                if len(part) < 1 or len(part) > 4:
                    return False

                for ch in part:
                    if ch not in valid:
                        return False

            return True

        if is_ipv4(queryIP):
            return "IPv4"

        if is_ipv6(queryIP):
            return "IPv6"

        return "Neither"
```

## Code Explanation

The IPv4 checker starts by splitting on dots:

```python
parts = ip.split(".")
```

A valid IPv4 address must have exactly four parts:

```python
if len(parts) != 4:
    return False
```

Then each part is validated.

Empty parts are invalid:

```python
if part == "":
    return False
```

Non-digit parts are invalid:

```python
if not part.isdigit():
    return False
```

Leading zeros are invalid when the part has more than one character:

```python
if len(part) > 1 and part[0] == "0":
    return False
```

The numeric range must be at most `255`:

```python
if int(part) > 255:
    return False
```

The IPv6 checker splits on colons:

```python
parts = ip.split(":")
```

A valid IPv6 address must have exactly eight parts:

```python
if len(parts) != 8:
    return False
```

Each part must have length from `1` to `4`:

```python
if len(part) < 1 or len(part) > 4:
    return False
```

Every character must be hexadecimal:

```python
if ch not in valid:
    return False
```

The main function checks IPv4 first, then IPv6:

```python
if is_ipv4(queryIP):
    return "IPv4"

if is_ipv6(queryIP):
    return "IPv6"

return "Neither"
```

## Alternative Implementation With Separator Choice

We can avoid running both validators in many cases by checking the separator first.

```python
class Solution:
    def validIPAddress(self, queryIP: str) -> str:
        if "." in queryIP:
            return "IPv4" if self._is_ipv4(queryIP) else "Neither"

        if ":" in queryIP:
            return "IPv6" if self._is_ipv6(queryIP) else "Neither"

        return "Neither"

    def _is_ipv4(self, ip: str) -> bool:
        parts = ip.split(".")

        if len(parts) != 4:
            return False

        for part in parts:
            if part == "":
                return False
            if not part.isdigit():
                return False
            if len(part) > 1 and part[0] == "0":
                return False
            if int(part) > 255:
                return False

        return True

    def _is_ipv6(self, ip: str) -> bool:
        parts = ip.split(":")

        if len(parts) != 8:
            return False

        valid = set("0123456789abcdefABCDEF")

        for part in parts:
            if not 1 <= len(part) <= 4:
                return False

            for ch in part:
                if ch not in valid:
                    return False

        return True
```

The first implementation is compact and works well.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.validIPAddress("172.16.254.1") == "IPv4"
    assert s.validIPAddress("2001:0db8:85a3:0:0:8A2E:0370:7334") == "IPv6"
    assert s.validIPAddress("256.256.256.256") == "Neither"

    assert s.validIPAddress("192.168.01.1") == "Neither"
    assert s.validIPAddress("192.168.1.00") == "Neither"
    assert s.validIPAddress("192.168@1.1") == "Neither"

    assert s.validIPAddress("2001:0db8:85a3::8A2E:037j:7334") == "Neither"
    assert s.validIPAddress("02001:0db8:85a3:0000:0000:8a2e:0370:7334") == "Neither"

    assert s.validIPAddress("1.1.1.1.") == "Neither"
    assert s.validIPAddress("1..1.1") == "Neither"
    assert s.validIPAddress("0.0.0.0") == "IPv4"
    assert s.validIPAddress("255.255.255.255") == "IPv4"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"172.16.254.1"` | Valid IPv4 |
| Valid long IPv6 | Valid IPv6 with mixed case |
| `"256.256.256.256"` | IPv4 parts out of range |
| `"192.168.01.1"` | IPv4 leading zero |
| `"192.168.1.00"` | IPv4 leading zero |
| `"192.168@1.1"` | Invalid IPv4 character |
| IPv6 with `::` | Empty IPv6 group is invalid here |
| IPv6 group length `5` | IPv6 group too long |
| Trailing dot | Empty IPv4 group |
| Double dot | Empty IPv4 group |
| `"0.0.0.0"` | Smallest IPv4 parts |
| `"255.255.255.255"` | Largest IPv4 parts |