How do you solve Restore IP Addresses?

Use a recursive DFS that tries segments of length 1 to 3 starting from the current index. For each segment, check if it is valid (no leading zeros unless single '0', and integer value ≤ 255). If valid, append to the current path and recurse for the next segment. When four segments are formed and the entire string is consumed, join the segments with dots and add to the result. Backtrack by removing the last segment before trying the next possibility.

What pattern does Restore IP Addresses use?

The Pattern: Backtracking (State Restoration) The Heuristic: For problems requiring all valid partitions or combinations, use backtracking with early pruning and always restore state after exploring each choice to avoid side effects between branches.

Restore IP Addresses — Backtracking

Q: What is the time complexity of Restore IP Addresses?

O(1). The maximum length of s is 20, and IP addresses have fixed 4 segments with max length 3 each, so the search space is bounded by a constant factor, making the algorithm effectively O(1) for practical input sizes.

Problem

Given a string s containing only digits, return all possible valid IP address combinations that can be formed by inserting dots into s such that each segment is a valid IP octet.

1 ≤ s.length ≤ 20
s consists only of digits.

Example

Input: s = "25525511135"

Output: ["255.255.11.135", "255.255.111.35"]

The brute-force approach would try all possible ways to insert three dots, resulting in many invalid IPs due to segment length or value constraints. The algorithm uses backtracking to build segments incrementally, pruning invalid paths early. For example, starting from index 0, it tries segments of length 1 to 3. It first tries '2', then recurses to build the next segment. When a segment is invalid (e.g., '256' or '00'), it backtracks immediately. When four valid segments are formed and the entire string is consumed, the current path is joined with dots and added to the result.

Approach

Straightforward Solution

A brute-force approach tries all ways to place three dots in the string, checking each resulting segment for validity. This leads to O(n^3) possibilities and is inefficient without pruning.

Core Observation

An IP address consists of exactly four segments, each between 0 and 255, with no leading zeros unless the segment is exactly '0'. The problem reduces to partitioning the string into four valid segments.

Path to Optimal

Preview

The key insight is to use backtracking to build segments one by one, pruning invalid segments early. By limiting segment length to 3 and checking validity immediately, the search space is drastically reduced…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive DFS that tries segments of length 1 to 3 starting from the current index. For each segment, check if it is valid (no leading zeros unless single '0', and integer value ≤ 255)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(1)

The maximum length of s is 20, and IP addresses have fixed 4 segments with max length 3 each, so the search space is bounded by a constant factor, making the algorithm effectively O(1) for practical input sizes.

Space

O(1)

The recursion stack depth is at most 4 (number of segments), and the path stores at most 4 segments. The output list size depends on the number of valid IPs but is not counted as auxiliary space.

Solution

Python

1class Solution:
  def restoreIpAddresses(self, s: str) -> List[str]:
      res = []
      path = []
5
      def dfs(i):
          if len(path) == 4:
              if i == len(s):
                  res.append(".".join(path))
              return
11
          for l in range(1, 4):
              if i + l > len(s):
                  break
15
              seg = s[i:i+l]
17
              if (seg[0] == '0' and l > 1) or int(seg) > 255:
                  continue
20
              path.append(seg)
              dfs(i + l)
              path.pop()
24
      dfs(0)
      return res

Step-by-Step Solution

1

Build Valid IP Segments via Depth-First Search with Pruning

3res = []
4path = []
6def dfs(i):
  if len(path) == 4:
      if i == len(s):
          res.append(".".join(path))
      return
  for l in range(1, 4):
      if i + l > len(s):
          break
      seg = s[i:i+l]
      if (seg[0] == '0' and l > 1) or int(seg) > 255:
          continue
      path.append(seg)
      dfs(i + l)
      path.pop()

Objective

To recursively explore all possible segmentations of the string into valid IP address segments, pruning invalid segments early.

Key Insight

Backtracking incrementally constructs segments by trying lengths 1 to 3 from the current index. Validity checks for leading zeros and numeric range immediately discard invalid segments, drastically reducing the search space. The recursion terminates when four segments are formed or the string is fully consumed, ensuring only valid IP addresses are collected. The path list acts as a temporary workspace that is restored after each recursive call to maintain correctness across branches.

Interview Quick-Check

Core Logic

Backtracking tries segments of length 1 to 3, pruning invalid segments (leading zeros or >255), and recurses to build the next segment until four valid segments cover the entire string.

State & Boundaries

The recursion stops when four segments are formed; if the entire string is consumed, the current path is a valid IP and added to results.

Common Pitfalls & Bugs

Failing to prune segments with leading zeros or values >255 leads to invalid IPs and incorrect results.

Complexity

Limiting segment length to 3 and pruning invalid segments early keeps the search space manageable despite the combinatorial nature.

2

Initiate Backtracking and Return All Valid IP Addresses

To start the recursive search from the beginning of the string and return the collected valid IP addresses.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 18 Critical

if (seg[0] == '0' and l > 1) or int(seg) > 255:

Check if the segment has a leading zero or exceeds 255.

This line is the critical pruning step that enforces IP address validity rules: segments cannot have leading zeros unless they are exactly '0', and must be ≤ 255. Without this check, invalid IPs would be generated, and the algorithm would waste time exploring invalid paths.

Line 23 Critical

path.pop()

Remove the last segment from the path to backtrack.

This line is the single most critical line in the backtracking algorithm; it restores the path state after recursion returns, enabling exploration of alternative branches without corrupting shared state.

Line 8 Critical

if i == len(s):

Check if the entire string has been consumed when four segments are formed.

Only if the entire string is used up do we have a valid IP address; partial consumption means invalid segmentation.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why must the algorithm prune segments with leading zeros or values greater than 255 during backtracking?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Restore IP Addresses from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Restore IP Addresses drill

or drill a free problem

1	`class Solution:`
2	`def restoreIpAddresses(self, s: str) -> List[str]:`
3	`res = []`
4	`path = []`
5
6	`def dfs(i):`
7	`if len(path) == 4:`
8	`if i == len(s):`
9	`res.append(".".join(path))`
10	`return`
11
12	`for l in range(1, 4):`
13	`if i + l > len(s):`
14	`break`
15
16	`seg = s[i:i+l]`
17
18	`if (seg[0] == '0' and l > 1) or int(seg) > 255:`
19	`continue`
20
21	`path.append(seg)`
22	`dfs(i + l)`
23	`path.pop()`
24
25	`dfs(0)`
26	`return res`

3	`res = []`
4	`path = []`
6	`def dfs(i):`
7	`if len(path) == 4:`
8	`if i == len(s):`
9	`res.append(".".join(path))`
10	`return`
12	`for l in range(1, 4):`
13	`if i + l > len(s):`
14	`break`
16	`seg = s[i:i+l]`
18	`if (seg[0] == '0' and l > 1) or int(seg) > 255:`
19	`continue`
21	`path.append(seg)`
22	`dfs(i + l)`
23	`path.pop()`