Watch 10 video solutions for Restore IP Addresses, a medium level problem involving String, Backtracking. This walkthrough by NeetCode has 49,750 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
"0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
Example 1:
Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"]
Example 2:
Input: s = "0000" Output: ["0.0.0.0"]
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"]
Constraints:
1 <= s.length <= 20s consists of digits only.Problem Overview: Given a string containing only digits, return all possible valid IP addresses that can be formed by inserting three dots. Each segment must be between 0 and 255 and cannot contain leading zeros unless the segment itself is "0".
Approach 1: Backtracking with Segment Validation (O(3^4) time, O(4) space)
This approach builds the IP address one segment at a time using backtracking. At each position in the string, try taking 1, 2, or 3 digits as the next segment. Validate the segment immediately: reject values greater than 255 and segments with leading zeros like "01". If the segment is valid, append it to the current path and recurse to build the next part. Stop when four segments are created and the entire string is consumed.
The key insight is aggressive pruning. Invalid segments are discarded early, which keeps the search space extremely small. Since an IP address always has exactly four parts and each part has at most three digits, the recursion depth is fixed. This makes the practical runtime constant, roughly 3^4 combinations. This pattern appears frequently in problems that generate structured combinations from a string.
Approach 2: Iterative Partitioning (O(n^3) time, O(1) space)
An alternative is to iterate over every possible placement of three dots using three nested loops. Each loop chooses the end index of a segment, effectively splitting the string into four parts. For every combination of split points, extract the four substrings and validate them individually: check length (1–3 digits), ensure no leading zeros, and confirm the numeric value is ≤255.
This approach avoids recursion and uses straightforward iteration. However, it still explores all segment boundary combinations and performs repeated substring validation. With the string length capped at 12, the complexity behaves like O(n^3) due to the three split positions. The implementation is simple but less flexible than recursive generation.
Recommended for interviews: Backtracking is the expected solution. It demonstrates control over recursion, pruning, and structured search. Interviewers want to see you limit invalid branches early rather than brute-force every split. The iterative version works, but the backtracking approach communicates stronger problem‑solving instincts.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Segment Validation | O(3^4) ≈ O(1) | O(4) | Interview-preferred solution. Efficient pruning and clean recursive structure. |
| Iterative Dot Placement | O(n^3) | O(1) | Good when recursion is avoided or when demonstrating simple brute-force partitioning. |