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.
1import java.util.*;
2
3public class RestoreIPAddresses {
4 public List<String> restoreIpAddresses(String s) {
5 List<String> result = new ArrayList<>();
6 backtrack(result, new ArrayList<>(), s, 0);
7 return result;
8 }
9
10 private void backtrack(List<String> result, List<String> temp, String s, int start) {
11 if (temp.size() == 4) {
12 if (start == s.length()) {
13 result.add(String.join(".", temp));
14 }
15 return;
16 }
17
18 for (int len = 1; len <= 3; len++) {
19 if (start + len > s.length()) break;
20 String part = s.substring(start, start + len);
21 if ((part.startsWith("0") && part.length() > 1) || Integer.parseInt(part) > 255) continue;
22 temp.add(part);
23 backtrack(result, temp, s, start + len);
24 temp.remove(temp.size() - 1);
25 }
26 }
27
28 public static void main(String[] args) {
29 RestoreIPAddresses rip = new RestoreIPAddresses();
30 System.out.println(rip.restoreIpAddresses("25525511135"));
31 }
32}This Java solution employs backtracking similar to the above Python solution. We use a helper backtrack method that adds potential IP segments (temp) to the result list, if valid. We try segments of length 1 to 3 unless they lead to invalid segments (starting with zero, etc.). Once a complete 4-segment IP is built, it is added to result if it consumes all input characters.
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.
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
vector<string> restoreIpAddresses(string s) {
vector<string> result;
int n = s.size();
for (int i = 1; i < 4 && i < n - 2; ++i) {
for (int j = i + 1; j < i + 4 && j < n - 1; ++j) {
for (int k = j + 1; k < j + 4 && k < n; ++k) {
string s1 = s.substr(0, i);
string s2 = s.substr(i, j - i);
string s3 = s.substr(j, k - j);
string s4 = s.substr(k);
if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
result.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
}
}
}
}
return result;
}
bool isValid(const string &s) {
if (s.size() > 3 || (s[0] == '0' && s.size() > 1) || stoi(s) > 255) {
return false;
}
return true;
}
int main() {
vector<string> result = restoreIpAddresses("25525511135");
for (const string &ip : result) {
cout << ip << endl;
}
return 0;
}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 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).