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

Function shape:

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

Examples

Example 1:

s = "25525511135"

Valid answers:

[
    "255.255.11.135",
    "255.255.111.35",
]

Example 2:

s = "0000"

Each segment must be "0".

Answer:

["0.0.0.0"]

Example 3:

s = "101023"

Valid answers:

[
    "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:

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:

At each call, try the next segment length:

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.

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

    return int(segment) <= 255

Examples:

Algorithm

Create:

ans = []
path = []

Define:

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:

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:

remaining_chars < remaining_parts

or:

remaining_chars > remaining_parts * 3

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

Walkthrough

Use:

s = "101023"

Start with:

path = []
start = 0

Try first segment "1":

path = ["1"]
start = 1

Now try "0":

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

Now try "1":

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":

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

The final segment is "23".

So we get:

"1.0.10.23"

Backtracking continues and finds:

"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:

3^4 = 81

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

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

Implementation

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:

ans = []

The current partial IP address is:

path = []

The helper checks one segment:

def valid(segment: str) -> bool:

Leading zeroes are rejected:

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

Then the numeric range is checked:

return int(segment) <= 255

The recursive function starts at an index in s:

def backtrack(start: int) -> None:

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

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

Then:

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:

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

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

for length in range(1, 4):

Extract the candidate segment:

segment = s[start:end]

If valid, choose it and recurse:

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.

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: