DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Restore IP Addresses

mediumStrings

Problem statement

You get a string s made only of digits. Insert exactly three dots into it to form a valid IPv4 address, without adding, removing or reordering any digits. Return every address you can form, in any order.

Each of the four parts must be a number from 0 to 255 with no leading zero (a part can be 0, but not 00 or 01).

Examples

Example 1

Input: s = "11211"

Output: ["1.1.2.11", "1.1.21.1", "1.12.1.1", "11.2.1.1"]

Explanation: Five digits split into four parts means exactly one part has two digits, and every choice is valid.

Example 2

Input: s = "0100"

Output: ["0.1.0.0"]

Explanation: The only split into four parts is 0, 1, 0, 0. Any part like "01" or "00" would have a leading zero.

Hints

Approach

Backtracking with pruning. Build the address one part at a time. At each step try a part length of 1, 2 or 3, skip it if the part is invalid, and recurse on the rest of the string.

  1. If s has fewer than 4 or more than 12 digits, return [] immediately.
  2. build(start, parts): if there are 4 parts, record the address only if start == n.
  3. Prune: with left = 4 - len(parts) parts still to place, the remaining n - start digits must be between left and 3 * left. Otherwise return.
  4. For each length 1 to 3: take the piece, stop if it has a leading zero or exceeds 255, and recurse.

There are at most 3 choices for each of 4 parts, so at most 81 paths, whatever the input. Once the length check passes, the work is bounded by a constant.

ComplexityTime O(1)Space O(1)
Python
class Solution:
def restoreIpAddresses(self, s: str) -> list[str]:
n = len(s)
result = []
if n < 4 or n > 12:
return result
def build(start: int, parts: list[str]) -> None:
left = 4 - len(parts)
if left == 0:
if start == n:
result.append(".".join(parts))
return
if not left <= n - start <= 3 * left: # too few or too many digits remain
return
for length in (1, 2, 3):
piece = s[start:start + length]
if len(piece) < length:
break
if length > 1 and piece[0] == "0": # leading zero: longer pieces fail too
break
if int(piece) > 255:
break
parts.append(piece)
build(start + length, parts)
parts.pop()
build(0, [])
return result

Follow-up questions

  • Return only the addresses that fall inside a private range such as 10.0.0.0/8 or 192.168.0.0/16.
  • Count the valid addresses without building the strings.

Frequently asked questions

A valid input has 4 to 12 digits, and longer or shorter strings are rejected before any search. Within that range the recursion has at most 3 choices at each of 4 levels, so the work has a fixed upper bound.

Pieces are tried shortest first. If a piece has a leading zero or is over 255, every longer piece from the same start has the same problem, so there is nothing left to try at this position.

It combines IPv4 rules, which network and platform engineers are expected to know cold, with a small, well-bounded backtracking search. It also invites a follow-up about recovering addresses from logs or exports where the dots were stripped.