LeetCode #93 Medium

Restore IP Addresses

Insert three dots into a digit string to produce every valid IPv4 address.

stringbacktrackingrecursion

02

Intuition

Choosing three dot positions blindly creates combinations that can be rejected much earlier. Each IPv4 address contains exactly four segments, each using one to three digits and representing 0 through 255. Backtracking can build one validated segment at a time. Remaining-length bounds prune branches that cannot possibly fill the remaining segment slots.

How to spot this pattern

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.

03

Approach

1

Track the next digit and completed segments

The recursive state contains a string index and a list of chosen segments. Success occurs only when four segments use every input digit.

2

Try segment lengths one through three

Slice each available candidate, reject a multi-digit candidate beginning with zero, and reject numeric values above 255. Append a valid segment, recurse, then remove it to explore the next length.

3

Prune impossible remaining lengths

Before branching, compare remaining digits with remaining segments. Fewer than one digit per slot or more than three digits per slot makes completion impossible.

04

Solution

▶1class Solution:
▶2    def restoreIpAddresses(self, s: str) -> List[str]:
▶3        result = []
▶4        parts = []
▶5 
▶6        def search(index):
▶7            slots = 4 - len(parts)
▶8            remaining = len(s) - index
▶9            if remaining < slots or remaining > 3 * slots:
▶10                return
▶11            if len(parts) == 4:
▶12                if index == len(s):
▶13                    result.append('.'.join(parts))
▶14                return
▶15            for length in range(1, 4):
▶16                if index + length > len(s):
▶17                    break
▶18                segment = s[index:index + length]
▶19                if len(segment) > 1 and segment[0] == '0':
▶20                    break
▶21                if int(segment) > 255:
▶22                    break
▶23                parts.append(segment)
▶24                search(index + length)
▶25                parts.pop()
▶26 
▶27        search(0)
▶28        return result

05

Common pitfalls

Allowing leading zeros

✗ Wrong

if int(segment) <= 255:

✓ Right

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

IPv4 segments may be zero but cannot contain leading zeroes.

Accepting four segments before consuming all digits

✗ Wrong

if len(parts) == 4:
    result.append('.'.join(parts))

✓ Right

if len(parts) == 4:
    if index == len(s):
        result.append('.'.join(parts))

Unused trailing digits make the address invalid.

Trying arbitrarily long segments

✗ Wrong

for end in range(index + 1, len(s) + 1):

✓ Right

for length in range(1, 4):

An IPv4 segment contains at most three digits.

06

Edge cases

Segment text 0

Accept it, while rejecting longer forms such as 00 and 01.

A candidate above 255

Reject that segment and, since longer candidates only grow, stop trying longer lengths at that position.

Input length outside 4 through 12

Remaining-length pruning rejects it immediately.

07

Complexity

Time

O(1)

Space

O(1)

IPv4 has exactly four segments of at most three digits, so the search tree is bounded independently of larger input.