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.
This approach utilizes backtracking to explore all possible placements of the three dots in the string. We attempt to generate valid IP segments recursively, ensuring each generated segment maintains the restrictions of a valid IP address. By backtracking, we can explore each possible path of placing dots and ensure we cover all potential valid configurations.
This Python function defines a helper function backtrack, which takes the current starting index and a list of constructed IP parts. We recursively attempt to build valid segments, ensuring they adhere to IP rules (no leading zeros, within [0, 255] range), and append valid results to the result list. We explore segments of lengths 1 to 3, backtracking appropriately.
Java
Time Complexity: O(2^n), due to the exponential number of ways to split the string, though practical time for small strings like ours is quite feasible.
Space Complexity: O(n), for the recursion stack and to store the IP parts temporarily.
In this approach, we iterate through potential splits for the three dots required to form four IP sections. For each potential set of positions, we validate and construct the IP address. Although typically not as elegant as the recursive backtracking solution, it's systematic and allows us to explore and validate possible IP addresses through combinatorial checks.
This C++ solution uses a three-level nested loop to estimate possible positions of dots for dividing the string into four parts. For each configuration, it calls a helper function isValid to check if each part is a valid IP section (not exceeding 255 and no leading zero unless the part is zero itself).
JavaScript
Time Complexity: O(n^3), given the triple nested loop for positions.
Space Complexity: O(1), ignoring the output list space.
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(2^n), due to the exponential number of ways to split the string, though practical time for small strings like ours is quite feasible. |
| Iterative Approach | Time Complexity: O(n^3), given the triple nested loop for positions. |
| 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. |
Restore IP Addresses - Leetcode 93 - Python • NeetCode • 49,750 views views
Watch 9 more video solutions →Practice Restore IP Addresses with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor