LeetCode 93 - Restore IP Addresses

Difficulty: 🟡 Medium
Topics: String, Backtracking

Solution

Problem Understanding

The problem asks us to take a string containing only digits and determine every possible way to insert exactly three dots so that the resulting string becomes a valid IPv4 address.

A valid IP address has four numeric segments separated by dots. Each segment must satisfy two conditions:

Its numeric value must be between 0 and 255 inclusive.
It cannot contain leading zeros unless the segment itself is exactly "0".

For example:

"192.168.1.1" is valid because every segment is within range and contains no leading zeros.
"01.2.3.4" is invalid because "01" contains a leading zero.
"256.1.1.1" is invalid because 256 is greater than 255.

The input is a single string s made only of digits. We are not allowed to rearrange digits or delete characters. We can only insert dots at certain positions.

The output should contain every valid IP address that can be formed from the string.

The constraints provide important insight:

An IP address always contains exactly 4 segments.
Each segment can contain at most 3 digits.
Therefore, the longest possible valid IP string has length 12.
The shortest possible valid IP string has length 4.

Even though the official constraint allows strings up to length 20, any string longer than 12 can immediately return an empty result because it cannot possibly fit into four valid segments.

Several edge cases are important:

Strings containing many zeros, such as "0000", because leading zero handling is tricky.
Segments equal to "255" are valid, while "256" is not.
Strings too short or too long to form four segments.
Inputs where some partitions create leading zeros, such as "010010".

A naive implementation often fails on leading zero validation or accidentally allows segments larger than 255.

Approaches

Brute Force Approach

The brute force approach tries every possible way to place three dots in the string.

Since an IP address has four parts, we can choose:

The end of the first segment
The end of the second segment
The end of the third segment

The remaining characters become the fourth segment.

For every possible partition, we check whether all four segments are valid.

A segment is valid if:

Its length is between 1 and 3
Its numeric value is at most 255
It has no leading zeros unless it is exactly "0"

This approach is correct because it exhaustively checks every possible dot placement. However, it performs unnecessary work because many invalid paths are explored even after it becomes obvious they cannot produce a valid IP address.

Optimal Backtracking Approach

The key insight is that the problem naturally forms a recursive decision tree.

At every step, we decide how many digits to take for the current segment:

1 digit
2 digits
3 digits

We then recursively build the next segment.

Backtracking works well because:

We only need exactly four segments.
Each segment has strict validity rules.
Invalid paths can be pruned immediately.

For example:

If a segment starts with '0', we should stop after considering the single digit "0".
If a segment becomes larger than 255, we stop exploring that branch.

This pruning dramatically reduces unnecessary computation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	At most a fixed number of partitions, but explores all combinations without pruning
Optimal	O(1)	O(1)	Backtracking with pruning, explores only valid segment constructions

Although the complexities are technically constant because the maximum input length is bounded by 12 for valid processing, the backtracking approach is significantly cleaner and more efficient in practice.

Algorithm Walkthrough

First, check whether the string length is valid for an IP address. If the length is less than 4 or greater than 12, immediately return an empty list because no valid IP address can exist.
Start a backtracking function with three pieces of information:

The current index in the string
The segments chosen so far
The result list

If we already have 4 segments:

Check whether we have consumed the entire string.
If yes, join the segments using dots and add the IP address to the result.
If characters remain, this path is invalid.

For the current segment, try taking 1, 2, or 3 digits from the current index.
For each candidate segment:

Ensure we do not go past the end of the string.
Reject segments with leading zeros unless the segment is exactly "0".
Convert the segment to an integer and ensure it is at most 255.

If the segment is valid:

Add it to the current path.
Recursively process the next part of the string.
Remove the segment afterward to restore state for the next choice.

Continue until all valid combinations are explored.

Why it works

The algorithm works because every recursive call represents a partial IP address construction. At each step, we only extend the path using valid segments. Since every possible valid segment length from 1 to 3 is explored, every valid IP address is eventually generated. Invalid paths are discarded immediately, ensuring correctness and efficiency.

Python Solution

from typing import List

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []

        if len(s) < 4 or len(s) > 12:
            return result

        def backtrack(index: int, segments: List[str]) -> None:
            if len(segments) == 4:
                if index == len(s):
                    result.append(".".join(segments))
                return

            for length in range(1, 4):
                if index + length > len(s):
                    break

                segment = s[index:index + length]

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

                if int(segment) > 255:
                    continue

                segments.append(segment)
                backtrack(index + length, segments)
                segments.pop()

        backtrack(0, [])

        return result

The implementation begins with an early length check. Since a valid IP address requires exactly four segments and each segment can contain at most three digits, any string outside the range [4, 12] can be rejected immediately.

The backtrack function recursively builds candidate IP addresses. The index variable tracks how much of the input string has been consumed, while segments stores the currently selected parts of the IP address.

The base case occurs when four segments have already been chosen. At that point, the algorithm checks whether the entire string has been used. If so, the segments are joined with dots and added to the result list.

Inside the loop, the algorithm tries segment lengths of 1, 2, and 3. This matches the rules of IPv4 addresses because each segment can contain at most three digits.

The leading zero validation is especially important. If a segment has more than one character and starts with '0', it is skipped immediately.

The numeric range validation ensures that no segment exceeds 255.

The append and pop operations implement classic backtracking behavior. After exploring one branch recursively, the segment is removed so that the next branch starts with a clean state.

Go Solution

package main

import (
	"strconv"
	"strings"
)

func restoreIpAddresses(s string) []string {
	var result []string

	if len(s) < 4 || len(s) > 12 {
		return result
	}

	var backtrack func(index int, segments []string)

	backtrack = func(index int, segments []string) {
		if len(segments) == 4 {
			if index == len(s) {
				result = append(result, strings.Join(segments, "."))
			}
			return
		}

		for length := 1; length <= 3; length++ {
			if index+length > len(s) {
				break
			}

			segment := s[index : index+length]

			if len(segment) > 1 && segment[0] == '0' {
				continue
			}

			value, _ := strconv.Atoi(segment)

			if value > 255 {
				continue
			}

			segments = append(segments, segment)
			backtrack(index+length, segments)
			segments = segments[:len(segments)-1]
		}
	}

	backtrack(0, []string{})

	return result
}

The Go implementation follows the same recursive structure as the Python version. The main difference is slice handling.

In Go, slices are mutable views over arrays, so after appending a segment, we explicitly shrink the slice using:

segments = segments[:len(segments)-1]

This restores the previous state during backtracking.

The strconv.Atoi function converts string segments into integers for range validation. Since the input contains only digits, conversion errors are impossible in this problem.

The result slice is initialized as an empty slice rather than nil, which ensures clean return behavior.

Worked Examples

Example 1

Input:

s = "25525511135"

The algorithm explores possible segments recursively.

Step	Current Segments	Remaining String	Action
1	`[]`	`"25525511135"`	Try `"2"`, `"25"`, `"255"`
2	`["255"]`	`"25511135"`	Valid segment
3	`["255", "255"]`	`"11135"`	Valid segment
4	`["255", "255", "11"]`	`"135"`	Valid segment
5	`["255", "255", "11", "135"]`	`""`	Valid IP found
6	`["255", "255", "111"]`	`"35"`	Valid segment
7	`["255", "255", "111", "35"]`	`""`	Valid IP found

Final result:

["255.255.11.135", "255.255.111.35"]

Example 2

Input:

s = "0000"

Step	Current Segments	Remaining String	Action
1	`[]`	`"0000"`	Only `"0"` valid
2	`["0"]`	`"000"`	Only `"0"` valid
3	`["0", "0"]`	`"00"`	Only `"0"` valid
4	`["0", "0", "0"]`	`"0"`	Only `"0"` valid
5	`["0", "0", "0", "0"]`	`""`	Valid IP found

Final result:

["0.0.0.0"]

Example 3

Input:

s = "101023"

Some explored paths:

Current Segments	Next Candidate	Result
`[]`	`"1"`	Continue
`["1"]`	`"0"`	Continue
`["1", "0"]`	`"10"`	Continue
`["1", "0", "10"]`	`"23"`	Valid IP
`["1", "0"]`	`"102"`	Continue
`["1", "0", "102"]`	`"3"`	Valid IP
`["10"]`	`"1"`	Continue
`["10", "1"]`	`"0"`	Continue
`["10", "1", "0"]`	`"23"`	Valid IP

Final result:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	The number of recursive states is bounded because IP addresses have only 4 segments
Space	O(1)	Recursion depth is at most 4, excluding output storage

The complexity is technically constant because the input size relevant to valid processing is capped at 12 characters. Each recursive call explores at most 3 segment lengths, and recursion depth never exceeds 4. Therefore, the total number of explored states is bounded by a small constant.

The auxiliary space usage is also constant because the recursion stack and current segment list never grow beyond 4 elements.

Test Cases

from typing import List

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []

        if len(s) < 4 or len(s) > 12:
            return result

        def backtrack(index: int, segments: List[str]) -> None:
            if len(segments) == 4:
                if index == len(s):
                    result.append(".".join(segments))
                return

            for length in range(1, 4):
                if index + length > len(s):
                    break

                segment = s[index:index + length]

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

                if int(segment) > 255:
                    continue

                segments.append(segment)
                backtrack(index + length, segments)
                segments.pop()

        backtrack(0, [])

        return result

solution = Solution()

# Provided example
assert sorted(solution.restoreIpAddresses("25525511135")) == sorted([
    "255.255.11.135",
    "255.255.111.35"
])  # standard valid example

# All zeros
assert solution.restoreIpAddresses("0000") == [
    "0.0.0.0"
]  # verifies leading zero handling

# Mixed possibilities
assert sorted(solution.restoreIpAddresses("101023")) == sorted([
    "1.0.10.23",
    "1.0.102.3",
    "10.1.0.23",
    "10.10.2.3",
    "101.0.2.3"
])  # multiple valid partitions

# Too short
assert solution.restoreIpAddresses("123") == []  # cannot form 4 segments

# Too long
assert solution.restoreIpAddresses("1234567890123") == []  # exceeds maximum length

# Segment exceeds 255
assert solution.restoreIpAddresses("256256256256") == []  # all segments invalid

# Leading zero cases
assert sorted(solution.restoreIpAddresses("010010")) == sorted([
    "0.10.0.10",
    "0.100.1.0"
])  # ensures leading zeros rejected correctly

# Maximum valid segment values
assert solution.restoreIpAddresses("255255255255") == [
    "255.255.255.255"
]  # largest valid IP

# Multiple small segments
assert sorted(solution.restoreIpAddresses("1111")) == sorted([
    "1.1.1.1"
])  # smallest valid length

Test	Why
`"25525511135"`	Standard example with multiple valid outputs
`"0000"`	Verifies leading zero handling
`"101023"`	Tests many branching possibilities
`"123"`	Input too short
`"1234567890123"`	Input too long
`"256256256256"`	Segments exceed allowed range
`"010010"`	Complex leading zero behavior
`"255255255255"`	Maximum valid segment values
`"1111"`	Smallest valid input length

Edge Cases

Leading Zeros

Inputs containing zeros are one of the most common sources of bugs. For example, "01" is not a valid segment even though its integer value is 1. A naive implementation might accidentally allow it.

The solution handles this by checking:

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

This ensures that only the single character "0" is allowed.

Segments Larger Than 255

An IP segment must remain within the range [0, 255]. Strings like "256" or "999" must be rejected.

The implementation converts each candidate segment into an integer and immediately skips any value larger than 255.

This pruning prevents invalid paths from continuing deeper into recursion.

Strings With Invalid Length

A valid IP address requires exactly four segments, each containing between 1 and 3 digits.

That means:

Minimum length is 4
Maximum length is 12

Inputs outside this range can never produce valid answers. Without this early check, the recursive algorithm would waste time exploring impossible states.

The implementation handles this immediately at the beginning:

if len(s) < 4 or len(s) > 12:
    return result

This makes the solution more efficient and avoids unnecessary recursion.