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, generate all possible valid IPv4 addresses by inserting three dots. Each address must contain exactly four segments, and each segment must be between 0 and 255 without leading zeros (except the number 0 itself).
Approach 1: Backtracking (O(n^3) time, O(1) extra space)
This approach builds the IP address segment by segment using backtracking. Start from the first character and try to take 1, 2, or 3 digits as the next segment. After selecting a segment, validate it: the integer must be ≤255 and must not contain leading zeros like "01". If the segment is valid, recursively continue building the next part until four segments are formed.
The recursion stops when either four segments are created or the string is fully consumed. If both conditions match simultaneously, join the segments using dots and add the result to the output. Because each segment can only be length 1–3 and there are exactly four segments, the search space is small. This method systematically explores combinations while pruning invalid branches early.
This solution heavily relies on string slicing and validation checks. Interviewers expect candidates to reason about constraints such as segment length, leading zeros, and numeric bounds. The recursion depth is at most four, so auxiliary space remains constant aside from the output list.
Approach 2: Iterative Split Enumeration (O(n^3) time, O(1) extra space)
An alternative approach avoids recursion and instead enumerates all possible ways to place three dots using nested loops. Use three indices i, j, and k to represent split points in the string. These indices define four segments: s[0:i], s[i:j], s[j:k], and s[k:n]. Each segment must be length 1–3, so the loops only explore valid boundaries.
For every split combination, validate the four segments individually. Convert each substring to an integer and check the constraints: value ≤255 and no leading zeros unless the segment is exactly "0". If all segments pass validation, combine them into a dotted string and add it to the result list.
This method performs explicit enumeration instead of recursion, which some developers find easier to reason about during debugging. It still relies on careful string manipulation and boundary checks.
Recommended for interviews: The backtracking solution is the expected answer. It demonstrates control over recursive state exploration and pruning invalid candidates early. The iterative split method also works and shows strong reasoning about segment boundaries, but backtracking better reflects the pattern interviewers associate with constrained combinatorial generation problems.
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.
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).
C++
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 | O(n^3) | O(1) auxiliary (depth ≤ 4) | Best general solution. Cleanly explores segment combinations with early pruning. |
| Iterative Split Enumeration | O(n^3) | O(1) | When recursion is avoided and you want explicit control over split indices. |
Restore IP Addresses - Leetcode 93 - Python • NeetCode • 59,514 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