Abstract / Summary

Given a string of digits, list all possible valid IP addresses by inserting three dots into the string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (1+ million submissions).

Typical patterns to solve this problem:

• Backtracking
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a depth-first search that enumerates all possible ways to insert three dots into a numeric string so that each resulting segment forms a valid IPv4 octet. The public method restoreIpAddresses initializes the search and returns the collected addresses. The core recursive routine deeper builds partial results while enforcing the numeric constraints of each octet.

Core Logic

Entry Point

def restoreIpAddresses(self, s: str) -> List[str]:
    self.result = []
    self.deeper(s, "", 0)
    return self.result

The method creates an empty list self.result, starts the recursion with the original string s, an empty prefix have, and a dot counter set to zero. When the recursion finishes, the accumulated list of valid addresses is returned.

Recursive Exploration

@cache
def deeper(self, s, have, dots):

The decorator @cache memoizes calls, preventing repeated work for identical (s, have, dots) triples. The parameters are:

• s - the remaining substring to process.
• have - the partially built address, including trailing dots after each completed segment.
• dots - the number of dots already placed.

Completion Condition

if dots == 3:
    if not s:
        return
    if s[0] == "0" and len(s) > 1:
        return
    if int(s) > 255:
        return
    self.result.append(have + s)
    return

When three dots have been placed, exactly one segment remains. The code checks that the segment is non-empty, does not contain a leading zero unless it is a single zero, and does not exceed the maximum value 255. If all checks pass, the full address is assembled by concatenating have and the final segment, then stored.

Early Termination

if not s:
    return

If the input string is exhausted before three dots are placed, the current path cannot yield a valid address and the recursion stops.

Pruning Based on Remaining Length

need = 4 - dots
if need*3 < len(s):
    return

At any point, the algorithm knows how many segments are still required (need). Since each segment can contain at most three characters, the remaining string must not be longer than need * 3. If it is, the branch is abandoned early, reducing the search space.

Handling a Leading Zero

if s[0] == "0":
    self.deeper(s[1:], have + s[:1] + ".", dots + 1)
    return

When the next character is '0', the only permissible segment is the single digit zero. The code forces the choice of a one-character segment, appends a dot, increments the dot count, and recurses on the rest of the string. This prevents illegal multi-digit segments that start with zero.

Exploring 1-, 2-, and 3-Digit Segments

for i in range(1, 4):
    if i == 3:
        if int(s[:i]) > 255:
            break
    self.deeper(s[i:], have + s[:i] + ".", dots + 1)

For non-zero leading characters, the loop attempts segment lengths of one, two, and three. When the length reaches three, an additional numeric bound check (int(s[:i]) > 255) ensures that values above 255 are discarded, and the loop terminates early because longer lengths are impossible. Each valid slice is appended with a dot, the dot counter is increased, and recursion proceeds with the remaining substring.

Edge Cases Addressed

• Empty input - The early if not s: guard prevents any processing when the original string is empty.
• Segments with leading zeros - The explicit branch for s[0] == "0" guarantees that a segment like "01" or "00" is never accepted.
• Maximum octet value - Both the final-segment check (int(s) > 255) and the three-digit loop guard (int(s[:i]) > 255) enforce the upper bound of 255.
• Insufficient characters - The pruning condition need*3 < len(s) eliminates paths where the remaining characters exceed the maximum allowed length for the pending segments.
• Exact length match - When the remaining characters exactly fit the needed segments (e.g., three characters left for one segment), the algorithm proceeds without unnecessary branching.

Performance Optimizations

The recursion is heavily trimmed by three mechanisms:

1. Memoization - The @cache decorator stores results of previously visited states, so identical subproblems are solved once. This is especially beneficial when the same suffix appears after different dot placements.

2. Length-based pruning - By calculating the minimal and maximal possible lengths for the remaining segments (need*3), the algorithm discards branches that cannot possibly form a valid address, avoiding exponential blow-up.

3. Early break on overflow - Within the loop that tries three-character segments, the moment a three-digit slice exceeds 255 the loop stops. This prevents unnecessary recursive calls for longer slices that would also be invalid.

Together, these strategies keep the search space tight, ensuring that only feasible segmentations are explored while reusing work wherever possible.

Imagine there is a big pile of numbers, and it is time to turn them into a special digital address that computers use to talk to each other. This address looks like four groups of numbers separated by little dots.

The computer starts by looking at all the numbers in a line. To make sure the address is correct, it tries different ways to slice the line into four pieces. It has a special rule that says each piece cannot be bigger than two hundred and fifty-five. It also makes sure there are no silly zeros at the very front of any group unless the group is just the number zero itself.

The computer explores different paths by taking one, two, or three numbers at a time and putting a dot after them. Every time it finishes adding a dot, it checks if it still has more work to do or if it has reached the very end of the line. If it reaches the end and the address looks perfect, it saves that address in a list. It keeps trying all the different combinations until it has found every possible version of the address that could exist. It is like a puzzle where the computer tries every piece in every spot until the whole picture is complete.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python				Java				TS
	WalkCCC	C++	Python				Java
	leetcode.ca	C++	Python	C#			Java			Go	TS
	LeetcodeHelp	C++	Python				Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python				Java
github	aylei				Rust
	begeekmyfriend							C
	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai						Java
	chenyanzhe	C++
	everthis					JS
	gaosq0604		Python
	Garvit244		Python
	halfrost									Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff								Scala
	qiyuangong		Python
	ruoru				Rust
	shreymehul			C#
	suxrobGM			C#
	vli02							C
	vthwang						Java
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
vli02	C
vthwang	Java
XiaotaoGuo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality