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.The key idea behind Restore IP Addresses is to generate all valid ways to split the string into four segments, each representing a number between 0 and 255. Since an IP address has exactly four parts, a backtracking strategy works well. At each step, choose a substring of length 1 to 3 and check whether it forms a valid segment.
While exploring possibilities, enforce the constraints: the number must be within 0–255 and cannot contain leading zeros (except the number 0 itself). If a segment is valid, recursively continue building the remaining parts of the IP address. If four segments are formed and all characters are used, the combination becomes a valid result.
This pruning-based search ensures we only explore feasible paths. Because each segment can have at most three choices and the depth is fixed at four, the number of recursive states is small. The algorithm runs in roughly O(3^4) time with O(1) auxiliary space (excluding output), making it efficient for the problem constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with segment validation | O(3^4) (bounded exploration of segment choices) | O(1) auxiliary space, O(4) recursion depth |
NeetCode
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.
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.
1def restore_ip_addresses(s):
2 def backtrack(start, parts):
3 if len(parts) == 4:
4 if start == len(s):
5 result.append(".".join(parts))
6 return
7
8 for i in range(1, 4):
9 if start + i > len(s):
10 break
11 part = s[start:start+i]
12 if (len(part) > 1 and part[0] == '0') or (int(part) > 255):
13 continue
14 backtrack(start + i, parts + [part])
15
16 result = []
17 backtrack(0, [])
18 return result
19
20# Example usage:
21# restore_ip_addresses("25525511135")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.
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.
Time Complexity: O(n^3), given the triple nested loop for positions.
Space Complexity: O(1), ignoring the output list space.
1function restoreIpAddresses(s) {
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of Restore IP Addresses appear in coding interviews at companies like Amazon, Google, and Meta. It tests backtracking, string manipulation, and constraint validation, which are common themes in interview problems.
The optimal approach uses backtracking to try forming four valid segments from the string. At each step, you check if a substring of length 1–3 forms a valid number between 0 and 255 without leading zeros. Valid segments are recursively combined until a full IP address is formed.
Backtracking primarily uses recursion along with a temporary list or array to store the current segments. Strings and simple validation checks are sufficient, since the problem mainly involves exploring combinations with constraints.
Each segment of an IPv4 address must represent a number between 0 and 255. Since 255 is the largest valid value, no segment can exceed three digits, which helps limit the search space in the algorithm.
This JavaScript function constructs IP addresses using triple nested loops similar to the C++ solution. It calculates the potential dot positions, generates candidate segments, and verifies their validity using a custom isValid function before adding them to the result array if they form a valid IP address.