# LeetCode 93: Restore IP Addresses

## Problem Restatement

We are given a string `s` containing only digits.

We need to return all possible valid IP addresses that can be formed by inserting dots into `s`.

We cannot reorder digits.

We cannot remove digits.

We only insert exactly three dots so that the string becomes four valid IP address segments.

A valid IP address has exactly four integers separated by dots. Each integer must be between `0` and `255`, inclusive, and it cannot contain leading zeroes. The valid addresses may be returned in any order. The official constraints are `1 <= s.length <= 20`, and `s` contains only digits.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A digit string `s` |
| Output | All valid IP addresses formed from `s` |
| Segment count | Exactly `4` |
| Segment length | `1` to `3` digits |
| Segment value | `0` to `255` |
| Leading zero rule | `"0"` is valid, but `"00"` and `"01"` are invalid |

Function shape:

```python
class Solution:
    def restoreIpAddresses(self, s: str) -> list[str]:
        ...
```

## Examples

Example 1:

```python
s = "25525511135"
```

Valid answers:

```python
[
    "255.255.11.135",
    "255.255.111.35",
]
```

Example 2:

```python
s = "0000"
```

Each segment must be `"0"`.

Answer:

```python
["0.0.0.0"]
```

Example 3:

```python
s = "101023"
```

Valid answers:

```python
[
    "1.0.10.23",
    "1.0.102.3",
    "10.1.0.23",
    "10.10.2.3",
    "101.0.2.3",
]
```

## First Thought: Place Three Dots

An IP address has four parts.

So we can think of the problem as choosing four substrings from `s`.

For each segment, we can choose length:

```python
1, 2, or 3
```

because the largest valid segment is `255`, which has three digits.

After choosing four segments, the whole string must be used.

This is a small search tree, so backtracking fits naturally.

## Key Insight

At each step, choose the next IP segment.

The recursive state needs:

| State | Meaning |
|---|---|
| `start` | Current index in `s` |
| `path` | Segments chosen so far |
| `ans` | Valid IP addresses found |

At each call, try the next segment length:

```python
1
2
3
```

Then validate the segment.

A segment is valid if:

1. It has no leading zero unless it is exactly `"0"`.
2. Its integer value is at most `255`.

## Segment Validation

A helper function makes the logic clear.

```python
def valid(segment: str) -> bool:
    if len(segment) > 1 and segment[0] == "0":
        return False

    return int(segment) <= 255
```

Examples:

| Segment | Valid? | Reason |
|---|---:|---|
| `"0"` | Yes | Single zero is allowed |
| `"00"` | No | Leading zero |
| `"01"` | No | Leading zero |
| `"10"` | Yes | Between `0` and `255` |
| `"255"` | Yes | Maximum valid value |
| `"256"` | No | Greater than `255` |

## Algorithm

Create:

```python
ans = []
path = []
```

Define:

```python
backtrack(start)
```

At each call:

1. If `len(path) == 4`, check whether `start == len(s)`.
2. If both are true, join the segments with dots and add to `ans`.
3. If four segments are already chosen but characters remain, stop.
4. Otherwise, try segment lengths `1`, `2`, and `3`.
5. If the segment is valid, append it to `path`.
6. Recurse from the next index.
7. Pop the segment to try another choice.

## Pruning

We can stop early when the remaining string length cannot fit the remaining segments.

Let:

```python
remaining_chars = len(s) - start
remaining_parts = 4 - len(path)
```

Each remaining segment needs at least one digit and at most three digits.

So the path is impossible if:

```python
remaining_chars < remaining_parts
```

or:

```python
remaining_chars > remaining_parts * 3
```

This pruning is not required for correctness, but it avoids useless calls.

## Walkthrough

Use:

```python
s = "101023"
```

Start with:

```python
path = []
start = 0
```

Try first segment `"1"`:

```python
path = ["1"]
start = 1
```

Now try `"0"`:

```python
path = ["1", "0"]
start = 2
```

Now try `"1"`:

```python
path = ["1", "0", "1"]
start = 3
```

The last segment would be `"023"`, which has a leading zero, so this route fails.

Backtrack and try `"10"`:

```python
path = ["1", "0", "10"]
start = 4
```

The final segment is `"23"`.

So we get:

```python
"1.0.10.23"
```

Backtracking continues and finds:

```python
"1.0.102.3"
"10.1.0.23"
"10.10.2.3"
"101.0.2.3"
```

## Correctness

The algorithm builds IP addresses by choosing four segments in order from the original string.

Every chosen segment is a contiguous substring of `s`, and the recursive call always moves `start` forward. Therefore, the algorithm never reorders or removes digits.

The algorithm adds an answer only when exactly four segments have been chosen and all characters have been consumed. Therefore, every returned string uses all digits and has exactly four segments.

Each segment is checked before it is added to `path`. The validation rejects leading zeroes and values above `255`. Therefore, every returned address is valid.

Now consider any valid IP address that can be formed from `s`. Its four segments have lengths between `1` and `3`. The backtracking loop tries all segment lengths `1`, `2`, and `3` at each step. Since all four segments are valid, the algorithm will accept each of them and follow the exact path that forms this address. So every valid address is generated.

Therefore, the algorithm returns exactly all valid IP addresses.

## Complexity

There are only four segments, and each segment has at most three length choices.

So the search space is bounded by:

```python
3^4 = 81
```

The input length can be up to `20`, but no valid IP address can use more than `12` digits.

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` relative to input length | At most `81` segment choices are explored |
| Space | `O(1)` extra | The recursion depth is at most `4` |
| Output space | `O(k)` | `k` valid addresses are returned |

It is also acceptable to describe the time as bounded by a small constant because IPv4 always has exactly four segments.

## Implementation

```python
class Solution:
    def restoreIpAddresses(self, s: str) -> list[str]:
        ans = []
        path = []

        def valid(segment: str) -> bool:
            if len(segment) > 1 and segment[0] == "0":
                return False

            return int(segment) <= 255

        def backtrack(start: int) -> None:
            remaining_chars = len(s) - start
            remaining_parts = 4 - len(path)

            if remaining_chars < remaining_parts:
                return

            if remaining_chars > remaining_parts * 3:
                return

            if len(path) == 4:
                if start == len(s):
                    ans.append(".".join(path))
                return

            for length in range(1, 4):
                end = start + length

                if end > len(s):
                    break

                segment = s[start:end]

                if not valid(segment):
                    continue

                path.append(segment)
                backtrack(end)
                path.pop()

        backtrack(0)
        return ans
```

## Code Explanation

The answer list stores completed IP addresses:

```python
ans = []
```

The current partial IP address is:

```python
path = []
```

The helper checks one segment:

```python
def valid(segment: str) -> bool:
```

Leading zeroes are rejected:

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

Then the numeric range is checked:

```python
return int(segment) <= 255
```

The recursive function starts at an index in `s`:

```python
def backtrack(start: int) -> None:
```

Pruning checks whether the remaining characters can fit the remaining segments:

```python
remaining_chars = len(s) - start
remaining_parts = 4 - len(path)
```

Then:

```python
if remaining_chars < remaining_parts:
    return

if remaining_chars > remaining_parts * 3:
    return
```

If four segments have been chosen, we only accept the path when all characters are used:

```python
if len(path) == 4:
    if start == len(s):
        ans.append(".".join(path))
    return
```

Then we try segment lengths `1`, `2`, and `3`:

```python
for length in range(1, 4):
```

Extract the candidate segment:

```python
segment = s[start:end]
```

If valid, choose it and recurse:

```python
path.append(segment)
backtrack(end)
path.pop()
```

The `pop()` undoes the choice so the next candidate can be tried.

## Testing

Because output order may vary, compare sorted lists.

```python
def check(s, expected):
    sol = Solution()
    result = sol.restoreIpAddresses(s)
    assert sorted(result) == sorted(expected)

def run_tests():
    check("25525511135", [
        "255.255.11.135",
        "255.255.111.35",
    ])

    check("0000", [
        "0.0.0.0",
    ])

    check("101023", [
        "1.0.10.23",
        "1.0.102.3",
        "10.1.0.23",
        "10.10.2.3",
        "101.0.2.3",
    ])

    check("1111", [
        "1.1.1.1",
    ])

    check("010010", [
        "0.10.0.10",
        "0.100.1.0",
    ])

    check("99999999999999999999", [])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"25525511135"` | Main example |
| `"0000"` | Zero segments are valid only as `"0"` |
| `"101023"` | Multiple valid segment lengths |
| `"1111"` | Exactly one digit per segment |
| `"010010"` | Leading-zero handling |
| Very long string | Cannot fit into four IP segments |