Compile Ready
Module 5 · String Backtracking

Restore IP Addresses

MediumProblem 11 of 17 8 min read ~20 min to solve LeetCode
BacktrackingStringPartitioningDFSPruning
Asked atAmazonGoogleMicrosoftMetaOracle

Problem Statement

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting exactly three dots. A valid IP address has exactly four integer segments, each segment is between 0 and 255, and a segment cannot have leading zeroes unless it is exactly 0.

Input

A digit string s with no dots already placed.

Output

A list of valid IP address strings in any order.

Constraints

  • •1 <= s.length <= 20
  • •s consists of digits only

Examples

Example 1

Input: 
s = 25525511135
Output: [255.255.11.135,255.255.111.35]
Explanation: Both addresses split the digits into four valid 0 through 255 segments with no leading zeroes.

Example 2

Input: 
s = 0000
Output: [0.0.0.0]
Explanation: Each segment must be the single digit **0**. Longer segments such as **00** are rejected because of leading zeroes.

Example 3

Input: 
s = 101023
Output: [1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3]
Explanation: The valid outputs are exactly the four-segment splits that consume all digits and obey the length, value, and leading-zero rules.

Learning Objectives

  • Recognise IP restoration as a constrained **choose a segment, recurse on the suffix** problem.
  • Use segment count and start index as the recursion state.
  • Prune by remaining length before trying segment values.
  • Validate each segment with length, leading-zero, and numeric range checks.

Intuition

Pattern Recognition

This is another cut and partition string problem, but the partition must have exactly four pieces. At each frame, choose the next segment length: 1, 2, or 3 digits. If that segment is valid, append it and recurse on the remaining suffix.

The constraints make pruning especially important. With k segments left, the remaining character count must be at least k and at most 3k. A segment like 01 is invalid before numeric parsing because of the leading zero rule, and a segment like 256 is invalid because it exceeds 255. The base case succeeds only when exactly four segments have been chosen and the entire string has been consumed.

Common mistakes

  • ×Accepting segments with leading zeroes such as **01** or **00**.
  • ×Recording an address after four segments even when some input digits remain unused.
  • ×Trying segment lengths beyond three digits and then relying on numeric checks alone.
  • ×Forgetting to remove the last chosen segment before trying the next sibling cut.

Algorithm Explanation

State

Each frame carries start, the next unconsumed character index, and segments, the list of chosen IP pieces so far. The number of remaining segments is 4 - segments.size(). A valid branch must eventually consume every character exactly once.

Recursion tree

For s = 101023, the root may choose 1, 10, or 101 as the first segment. Under first segment 1, the next character is 0, so the only valid second segment starting there is 0; candidates 01 and 010 are pruned by the leading-zero rule. From [1,0], choices 1, 10, and 102 lead to different suffixes. The branch [1,0,10,23] consumes the string and records 1.0.10.23, while a branch such as [1,0,1,0] has characters left after four segments and is rejected.

Pruning

Before trying a segment, compare the remaining characters with the remaining segment slots. If there are too few characters to give every slot one digit, or too many characters to fit into three digits per slot, return immediately. For each candidate segment, reject lengths greater than 3, multi-character segments starting with 0, and numeric values above 255.

Algorithm

  1. Start DFS with start = 0 and an empty segment list.
  2. Compute remaining characters and remaining segment slots; return if the length bounds cannot be satisfied.
  3. If four segments have been chosen, record an address only when start == s.length.
  4. Try segment lengths 1, 2, and 3 while staying inside the string.
  5. Reject a segment if it has a leading zero or if Integer.parseInt gives a value above 255.
  6. Append the valid segment, recurse from the next start index, then remove it.
  7. Build an address from four segments by joining them with the plain . character.

Solutions

Solution: Four-segment DFS with validity pruning

The DFS places one IP segment at a time. Because an IP address always has four segments and each segment has length 1 through 3, the branching factor is tiny; correctness comes from strict pruning of invalid segment shapes and from accepting only branches that consume the whole string.

Step-by-step

  1. Track the current index and the list of chosen segments.
  2. Use remaining-character bounds to stop branches that cannot possibly fill the remaining slots.
  3. If four segments are chosen, add an address only when the index is at the end of the string.
  4. Try segment lengths from 1 through 3.
  5. Validate leading zeroes and the numeric value 0 <= value <= 255.
  6. Choose the segment, recurse, and unchoose it before trying the next length.
Time

O(3^4)

Space

O(1)

There are at most 3 length choices for each of 4 segments. Auxiliary space is constant because recursion depth and path size are bounded by 4, excluding output.

Java implementation

Loading…

Dry Run

Sample input

s = 101023. Track segment choices, leading-zero pruning, and the requirement that four segments must consume the whole string.

depthstartsegmentpathaction
001[1]valid first segment, recurse from 1
110[1,0]single zero is allowed, recurse from 2
221[1,0,1]valid third segment, recurse from 3
330[1,0,1,0]four segments chosen but characters remain, prune
3302[1,0,1]leading zero, prune
2210[1,0,10]valid third segment, recurse from 4
3423[1,0,10,23]consumed whole string, record 1.0.10.23
22102[1,0,102]valid third segment, recurse from 5
353[1,0,102,3]consumed whole string, record 1.0.102.3
1101[1]leading zero, prune sibling segment
0010[10]valid first segment, explore another branch
00101[101]valid first segment, explore another branch

The DFS records only branches with four valid segments and no leftover characters. Leading-zero pruning removes many tempting but invalid cuts after a 0 digit.

Interview Tips

Name all three validity rules before coding: length at most three, numeric value at most 255, and no leading zero unless the segment is exactly 0. Then add the remaining-length bound because it demonstrates pruning maturity and prevents exploring branches that cannot fill exactly four segments.

Likely follow-ups

  • How would you adapt the method for IPv6-style groups with hexadecimal characters?
  • How would you return only the count of valid addresses?
  • How would the pruning change if the number of required segments were a parameter?
  • How would you validate a string that already contains dots instead of inserting them?

Similar Problems

Palindrome Partitioning
MediumAlso chooses a valid prefix segment and recurses on the remaining suffix.
Letter Combinations of a Phone Number
MediumAnother bounded-depth string generation problem.
Combinations
MediumShares fixed-depth selection with choose, recurse, and unchoose steps.
Split String Into Descending Consecutive Values
MediumAn advanced string-splitting problem with numeric validation and pruning.
Expression Add Operators
HardAlso cuts a digit string into numeric pieces before applying extra constraints.

Key Takeaways

  • Restore IP Addresses is fixed-depth string partitioning with aggressive validity pruning.
  • The base case requires both four segments and full input consumption.
  • Leading zeroes must be rejected before accepting a multi-character segment.
  • Remaining-length bounds are a simple way to cut impossible branches early.
Reusable template: Constrained segment DFS: choose a short valid prefix, recurse on the suffix with one fewer slot, and accept only when all slots are filled and the input is consumed.