DSA Restoring IP Addresses

The problem

Restoring IP addresses rebuilds every valid address hidden in one string of digits. An address has four segments joined by dots. A segment is one number from 0 to 255.

The answer in this article is the list of valid addresses in the order the search finds them. A segment with more than one digit may not start with zero. A string longer than 12 digits holds no valid address.

for s in ['25525511135', '101023', '0000', '1111']:
    print('input:', s, 'length:', len(s))

Each case is a plain digit string with no dots. The dots are exactly what the search must place. Three cut positions split the string into four segments.

Intuition: cut anywhere and check at the end

The first idea places three cuts in every possible way. It builds each full split first. Only then does it check the four segments.

The waste is the trap. A first segment of 256 already dooms the whole split. The idea still builds and checks every completion of that split before learning so.

s = '256111'
count = 0
total = 0
for a in range(1, len(s)):
    for b in range(a + 1, len(s)):
        for c in range(b + 1, len(s)):
            total += 1
            parts = [s[:a], s[a:b], s[b:c], s[c:]]
            if parts[0] == '256':
                count += 1
print('splits built in total:', total)
print('splits starting with segment 256:', count)
print('segment 256 valid:', 0 <= 256 <= 255)

Every split that starts with 256 is invalid before its other segments are read. Checking a segment as soon as it is cut removes those splits at the first step. That check is the core of the optimal search.

Brute force: every split, checked whole

The brute force enumerates every choice of three cut positions. It validates the complete split only. A counter records how many splits it built.

def brute(s):
    results = []
    built = [0]
    n = len(s)
    for a in range(1, n):
        for b in range(a + 1, n):
            for c in range(b + 1, n):
                built[0] += 1
                parts = [s[:a], s[a:b], s[b:c], s[c:]]
                ok = True
                for part in parts:
                    if len(part) > 3 or (len(part) > 1 and part[0] == '0') or int(part) > 255:
                        ok = False
                if ok:
                    results.append('.'.join(parts))
    return results, built[0]
for s in ['1111', '101023']:
    results, built = brute(s)
    print('input:', s, 'splits built:', built)
    for address in results:
        print(address)

The string 1111 builds 1 split and keeps 1 address. The string 101023 builds 10 splits and keeps 5 addresses. Longer strings build far more splits, most of them with an invalid early segment, and the brute force pays that cost on every input.

The optimal solution: backtrack segment by segment

Backtracking chooses the length of the next segment, from one to three digits, and a segment is checked the moment it is cut, so an invalid segment ends its branch at once. That one sentence is the whole method.

Four placed segments with no digits left form one complete address. Trying lengths in the order 1, 2, and 3 fixes the output order. Every choice is undone after its branch.

def restore(s):
    results = []
    calls = [0]
    def valid_segment(text):
        if len(text) > 1 and text[0] == '0':
            return False
        return 0 <= int(text) <= 255
    def search(start, parts):
        calls[0] += 1
        if len(parts) == 4:
            if start == len(s):
                results.append('.'.join(parts))
            return
        for length in (1, 2, 3):
            end = start + length
            if end > len(s):
                break
            piece = s[start:end]
            if valid_segment(piece):
                parts.append(piece)
                search(end, parts)
                parts.pop()
    search(0, [])
    return results, calls[0]
for s in ['25525511135', '101023', '0000', '1111']:
    results, calls = restore(s)
    print('input:', s, 'count:', len(results), 'calls:', calls)
    for address in results:
        print(address)

Every case from the start of the article is answered. The string 0000 gives one address, because only single zeros are valid segments. The string 1111 also gives one address, with each segment holding one digit.

Walkthrough: restoring 101023

The walk follows the first address found. The state is the list of placed segments and the position of the next digit. Each step cuts one valid segment.

s = '101023'
parts = []
start = 0
for piece in ['1', '0', '10', '23']:
    parts.append(piece)
    start += len(piece)
    print('placed:', list(parts), 'next digit index:', start)
print('address:', '.'.join(parts))

Four segments are placed and the next index is 6, the end of the string. That pair of facts makes the address complete. The search then undoes the last cut and tries the next length at that position.

Complexity

Each segment has at most three length choices, and an address has four segments, so the search makes at most 81 leaf choices and its time is a small constant for this problem. Its space is the four placed segments plus the recursion depth of four.

def calls_for(s):
    calls = [0]
    def valid(t):
        return not (len(t) > 1 and t[0] == '0') and int(t) <= 255
    def search(start, depth):
        calls[0] += 1
        if depth == 4:
            return
        for length in (1, 2, 3):
            end = start + length
            if end > len(s):
                break
            if valid(s[start:end]):
                search(end, depth + 1)
    search(0, 0)
    return calls[0]
for s in ['1111', '101023', '25525511135']:
    print('length', len(s), 'calls:', calls_for(s))

The call counts stay small at every length in this range. The segment check does the pruning. A string of thirteen digits is rejected by length alone, before any search.

Edge cases and pitfalls

A leading zero is the classic trap. The segment 01 looks numeric and is still invalid. Only the single digit 0 may start with zero, because it is zero itself.

A segment above 255 is the other trap. The value 256 fits in three digits and still fails. Both rules must be checked, and a length check alone catches neither.

def restore(s):
    if len(s) > 12 or len(s) < 4:
        return []
    results = []
    def valid(t):
        return not (len(t) > 1 and t[0] == '0') and int(t) <= 255
    def search(start, parts):
        if len(parts) == 4:
            if start == len(s):
                results.append('.'.join(parts))
            return
        for length in (1, 2, 3):
            end = start + length
            if end > len(s):
                break
            if valid(s[start:end]):
                parts.append(s[start:end])
                search(end, parts)
                parts.pop()
    search(0, [])
    return results
print('0000:', restore('0000'))
print('010:', restore('010'))
print('empty:', restore(''))
print('too long:', restore('1111111111111'))
print('segment check 01:', (len('01') > 1 and '01'[0] == '0'))
print('segment check 256:', 256 <= 255)

The string 010 gives no address, because it holds only three digits for four segments. The empty string and the over-long string also give no address. Each answer follows from the rules, with no special handling.