Restore IP Addresses
Restore IP Addresses: insert three dots into a digit string to produce every valid IPv4 address.
- 1 <= s.length <= 20
- s consists of digits only.
Intuition
Restore ip addresses asks for every valid IPv4 address obtainable by inserting three dots into a digit string. Choosing dot positions blindly generates many combinations that are invalid for reasons visible much earlier, so the work is in rejecting them promptly.
An IPv4 address is four segments, and the rules on each are tight: one to three digits, numeric value 0 to 255, and no leading zero unless the segment is exactly "0". That last rule is the one most often missed — "01" is not a valid segment even though 1 is a valid value.
Backtracking builds one validated segment at a time. From the current position, try consuming one, two or three digits; if the candidate passes all three rules, commit it and recurse for the next segment. Success is reaching four segments having consumed every digit — both conditions, since three segments covering the whole string is a failure just as four segments leaving digits behind is.
The pruning that keeps this fast is a length check before branching:
- With r segments remaining and d digits left, the branch is impossible unless r ≤ d ≤ 3r.
Fewer than one digit per remaining segment cannot fill them; more than three per segment cannot be consumed. Checking that up front kills entire subtrees before any recursion happens.
The string is at most 12 digits, so the search is tiny — but the validation rules are exactly what the problem is testing.
A string must be divided into a fixed number of locally constrained pieces. That is a natural backtracking partition problem, with strong pruning from minimum and maximum piece lengths.
Approach
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(1) time and O(1) space.
Track position and completed segments
The recursive state is the index of the next unconsumed digit plus the list of segments chosen so far. Both are needed — four segments is only a success if the index has also reached the end of the string.
Try segment lengths one to three
From the current index, slice candidates of one, two and three digits, stopping at the string's end. Each valid candidate is a branch; each invalid one is rejected before any recursion beneath it.
Apply all three validity rules
Reject a multi-digit candidate starting with '0', and reject any numeric value above 255. The leading-zero rule is the one most often forgotten — "01" is invalid despite representing a legal number.
Prune on remaining length
Before branching, check that the digits left fit the segments left: at least one and at most three digits per remaining segment. This kills whole subtrees before recursion, and is what keeps the search small.
Require four segments and no digits left
Record an address only when four segments have been chosen and every digit is consumed. Checking only the segment count accepts prefixes of the input as valid addresses.
Undo after each branch
Remove the appended segment before trying the next length, so sibling branches start clean. Forgetting the removal leaks segments between branches and produces addresses that were never actually built.
Cost of the constrained search
With at most three choices per segment across four segments, the tree is bounded at 3⁴ = 81 branches before pruning, so this is effectively O(1) for the 12-digit input limit. Space is O(1) beyond the output.
Solution & live demo
Common pitfalls
Allowing leading zeros
if int(segment) <= 255:
if len(segment) > 1 and segment[0] == '0':
breakIPv4 segments may be zero but cannot contain leading zeroes.
Accepting four segments before consuming all digits
if len(parts) == 4:
result.append('.'.join(parts))if len(parts) == 4:
if index == len(s):
result.append('.'.join(parts))Unused trailing digits make the address invalid.
Trying arbitrarily long segments
for end in range(index + 1, len(s) + 1):
for length in range(1, 4):
An IPv4 segment contains at most three digits.
Edge cases
0Accept it, while rejecting longer forms such as 00 and 01.
Reject that segment and, since longer candidates only grow, stop trying longer lengths at that position.
Remaining-length pruning rejects it immediately.