93. Restore IP Addresses

MediumBacktrackingDFS splitting a string into exactly four valid octetsSegment partitioning with validity pruning

Restore IP Addresses

Given a string s of only digits, return all possible valid IPv4 addresses formed by inserting three dots so the string splits into four parts. Each part must be between 0 and 255, cannot have a leading zero (unless it is exactly '0'), and no digits may be added, removed, or reordered.

Open official problem prompt ↗

In plain English

Enumerate every way to punctuate the digit string into four legal IPv4 octets.

Picture it like this

Slicing a fixed loaf into exactly four pieces where each piece must weigh within an allowed range; you try each cut position and discard slicings that break a rule.

Example

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Why: Both split the 11 digits into four parts each in 0-255 with no leading zeros; no other dot placement is valid.

Constraints

1 <= s.length <= 20s consists of digits only

Pattern lesson

See the pattern, then code

Segment partitioning with validity pruning

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. An IPv4 address is exactly four octets; recurse choosing the next segment length (1-3 digits), validate it (no leading zero, value <= 255), and only accept when four parts consume the whole string.

New words, made simpleKnow these before the algorithm

Octet: One of the four numeric parts of an IPv4 address, each in the range 0-255.
Leading zero rule: A segment longer than one digit may not start with '0', so '01' is invalid but '0' is fine.
Full consumption: A valid answer must use every digit, so four parts and start at end of string.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Triple nested loops over cut points

Works and is fast but the index arithmetic is error-prone and less general.

Choose three dot positions with three loops and validate the four resulting parts.

Time O(1) boundedSpace O(1)

Best choiceBacktracking over segment lengths

Clean, prunes early, and extends naturally to related partition problems.

Recurse choosing 1-3 digit segments, validating each and requiring four parts covering all digits.

Time O(1) bounded (<= 27 placements)Space O(1)

The rule we keep true

Invariant

parts always contains only validated octets, and start equals the total length of digits already consumed by those parts.

Why this is correct

Reasoning

Each recursive call appends only a segment passing the octet rules, so any path that reaches four parts is composed entirely of legal octets; requiring start == n at that point guarantees all digits are used and none invented, so exactly the valid addresses are emitted.

The algorithm in three movesSay these aloud before coding

1Recurse tracking the start index and the parts chosen so far

parts=['255'], start=3

2When four parts exist, accept only if the whole string is consumed

parts=['255','255'], start=6

3Otherwise try segment lengths 1, 2, and 3 from the current position

parts=['255','255','11'], start=8 -> last part '135' valid -> record

4Validate each segment: reject empty, length > 3, leading zeros, or value > 255

5Recurse with the segment appended; join with dots on success

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

510

1 · Readstart 0

2 · Askwhich 1-3 digit prefixes are valid?

3 · Update stateparts=[]

4 · Result'2','25','255' all <=255; follow '255' -> start 3

Key takeaway

The first octet claims digits 0-2 ('255'); the search then partitions the remaining eight digits into three more valid octets.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-3Init
res collects addresses; n caches the length for boundary checks.
2
Lines 4-9Segment validity
Rejects empty, over-length, leading-zero, and >255 segments in one helper.
3
Lines 10-14Base case
With four parts, accept only when every digit is consumed (start == n).
4
Lines 15-21Try lengths 1-3
Break when a length overruns the string; recurse on each valid segment, appending it to parts.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Strings too short (<4) or too long (>12) yield no addresses
'0000' -> only '0.0.0.0'
Segments like '256' or '011' must be rejected

Common beginner mistakes

Allowing leading zeros such as '01' or '00'
Accepting four parts without checking that the whole string was consumed
Treating values by string comparison instead of int, or forgetting the <=255 bound

Check your understanding

Why must we check start == n when four parts are collected instead of accepting immediately?

PyPython 3 · solution.py

Optimal

1class Solution:2    def restoreIpAddresses(self, s: str) -> list[str]:3        res: list[str] = []4        n = len(s)5        def valid(seg: str) -> bool:6            if not seg or len(seg) > 3:7                return False8            if len(seg) > 1 and seg[0] == '0':9                return False10            return int(seg) <= 25511        def backtrack(start: int, parts: list[str]) -> None:12            if len(parts) == 4:13                if start == n:14                    res.append('.'.join(parts))15                return16            for length in range(1, 4):17                if start + length > n:18                    break19                seg = s[start:start + length]20                if valid(seg):21                    backtrack(start + length, parts + [seg])22        backtrack(0, [])23        return res

Time complexityO(1) effectively - at most 3^3 = 27 dot placements bounded by fixed lengths, each O(1) to validateOptimized

Space complexityO(1) recursion depth (at most 4) plus outputExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftBloomberg

Restore IP Addresses

Restore IP Addresses

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking