Restore IP Addresses
Restore IP Addresses is a medium recursion & backtracking problem solved with the choice per position pattern.
The best approach, optimal (backtracking with pruning), runs in O(1) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every dot placement) up.
Problem
A valid IPv4 address is four integers separated by single dots. Each integer is between 0 and 255 and is written without leading zeros, so "10.0.7.255" is valid while "10.07.1.1" and "10.256.1.1" are not.
You are given a string s made only of digits. Insert exactly three dots into s (without reordering, adding or removing any digit) and return every valid IP address that can be formed. The addresses may be returned in any order.
Examples
Example 1
- Input
s = "2550255"- Output
["2.5.50.255", "2.55.0.255", "25.5.0.255", "25.50.2.55", "25.50.25.5", "255.0.2.55", "255.0.25.5"]- Why
- Every way to cut the seven digits into four parts that are each 0–255 with no leading zero.
Example 2
- Input
s = "10023"- Output
["1.0.0.23", "10.0.2.3"]- Why
- Splits like "1.00.2.3" or "100.2.3" are rejected: a part may not have a leading zero, and there must be four parts.
Example 3
- Input
s = "0000"- Output
["0.0.0.0"]- Why
- A single 0 is a valid part, so the only address uses four of them.
Constraints
1 <= s.length <= 20scontains digits only.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every dot placement) | O(1) | O(1) |
| Optimal (backtracking with pruning) | O(1) | O(1) |
1Brute force (try every dot placement)
O(1)At most 3 × 3 × 3 = 27 splits, each checked on at most 12 characters.O(1)Apart from the output, only the four substrings of the current split.Choose the lengths of the first three parts (each 1 to 3); the fourth part is whatever remains. Check all four parts and keep the address if every part is valid.
- Loop a, b, c over 1..3 (lengths of parts 1–3).
- The fourth part has length n - a - b - c; skip unless it is 1..3.
- Cut the four substrings and validate each one.
- If all four are valid, join them with dots and add to the answer.
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> out = new ArrayList<>();
int n = s.length();
for (int a = 1; a <= 3; a++)
for (int b = 1; b <= 3; b++)
for (int c = 1; c <= 3; c++) {
int d = n - a - b - c;
if (d < 1 || d > 3) continue;
String p1 = s.substring(0, a), p2 = s.substring(a, a + b);
String p3 = s.substring(a + b, a + b + c), p4 = s.substring(a + b + c);
if (ok(p1) && ok(p2) && ok(p3) && ok(p4)) out.add(p1 + "." + p2 + "." + p3 + "." + p4);
}
return out;
}
private boolean ok(String p) {
if (p.length() > 1 && p.charAt(0) == '0') return false;
return Integer.parseInt(p) <= 255;
}
}class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def ok(p: str) -> bool:
if len(p) > 1 and p[0] == '0':
return False
return int(p) <= 255
out = []
n = len(s)
for a in range(1, 4):
for b in range(1, 4):
for c in range(1, 4):
d = n - a - b - c
if d < 1 or d > 3:
continue
p1, p2 = s[:a], s[a:a + b]
p3, p4 = s[a + b:a + b + c], s[a + b + c:]
if ok(p1) and ok(p2) and ok(p3) and ok(p4):
out.append(p1 + "." + p2 + "." + p3 + "." + p4)
return outclass Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> out;
int n = s.size();
for (int a = 1; a <= 3; a++)
for (int b = 1; b <= 3; b++)
for (int c = 1; c <= 3; c++) {
int d = n - a - b - c;
if (d < 1 || d > 3) continue;
string p1 = s.substr(0, a), p2 = s.substr(a, b);
string p3 = s.substr(a + b, c), p4 = s.substr(a + b + c);
if (ok(p1) && ok(p2) && ok(p3) && ok(p4)) out.push_back(p1 + "." + p2 + "." + p3 + "." + p4);
}
return out;
}
private:
bool ok(const string& p) {
if (p.size() > 1 && p[0] == '0') return false;
return stoi(p) <= 255;
}
};function restoreIpAddresses(s) {
const ok = (p) => {
if (p.length > 1 && p[0] === '0') return false;
return parseInt(p, 10) <= 255;
};
const out = [];
const n = s.length;
for (let a = 1; a <= 3; a++)
for (let b = 1; b <= 3; b++)
for (let c = 1; c <= 3; c++) {
const d = n - a - b - c;
if (d < 1 || d > 3) continue;
const p1 = s.substring(0, a), p2 = s.substring(a, a + b);
const p3 = s.substring(a + b, a + b + c), p4 = s.substring(a + b + c);
if (ok(p1) && ok(p2) && ok(p3) && ok(p4)) out.push(p1 + "." + p2 + "." + p3 + "." + p4);
}
return out;
}2Optimal (backtracking with pruning)
O(1)The recursion tree has at most 3⁴ = 81 leaves, and pruning cuts most of them.O(1)Recursion depth is 4 and the current path holds 4 parts.Build the address one part at a time. From position start, try a part of length 1, 2 or 3; keep it only if it is a valid part, then recurse for the next part. Prune as soon as the remaining digits are too few or too many for the remaining parts (each part needs 1 to 3 digits).
- If the length is outside 4..12, return an empty list.
- dfs(start, parts): if 4 parts are chosen, record the address when start == n.
- Let left = 4 - parts. If n - start < left or n - start > 3 * left, return.
- Try len = 1..3: stop at a leading zero for len > 1 or a value above 255; otherwise push the part, recurse, pop.
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> out = new ArrayList<>();
if (s.length() < 4 || s.length() > 12) return out;
dfs(s, 0, new ArrayList<>(), out);
return out;
}
private void dfs(String s, int start, List<String> parts, List<String> out) {
int n = s.length(), left = 4 - parts.size();
if (left == 0) {
if (start == n) out.add(String.join(".", parts));
return;
}
if (n - start < left || n - start > 3 * left) return;
int val = 0;
for (int len = 1; len <= 3 && start + len <= n; len++) {
if (len > 1 && s.charAt(start) == '0') break;
val = val * 10 + (s.charAt(start + len - 1) - '0');
if (val > 255) break;
parts.add(s.substring(start, start + len));
dfs(s, start + len, parts, out);
parts.remove(parts.size() - 1);
}
}
}class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
n = len(s)
out = []
if n < 4 or n > 12:
return out
parts = []
def dfs(start: int) -> None:
left = 4 - len(parts)
if left == 0:
if start == n:
out.append(".".join(parts))
return
if n - start < left or n - start > 3 * left:
return
val = 0
for length in range(1, 4):
if start + length > n:
break
if length > 1 and s[start] == '0':
break
val = val * 10 + int(s[start + length - 1])
if val > 255:
break
parts.append(s[start:start + length])
dfs(start + length)
parts.pop()
dfs(0)
return outclass Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> out;
if (s.size() < 4 || s.size() > 12) return out;
vector<string> parts;
dfs(s, 0, parts, out);
return out;
}
private:
void dfs(const string& s, int start, vector<string>& parts, vector<string>& out) {
int n = s.size(), left = 4 - (int)parts.size();
if (left == 0) {
if (start == n) out.push_back(parts[0] + "." + parts[1] + "." + parts[2] + "." + parts[3]);
return;
}
if (n - start < left || n - start > 3 * left) return;
int val = 0;
for (int len = 1; len <= 3 && start + len <= n; len++) {
if (len > 1 && s[start] == '0') break;
val = val * 10 + (s[start + len - 1] - '0');
if (val > 255) break;
parts.push_back(s.substr(start, len));
dfs(s, start + len, parts, out);
parts.pop_back();
}
}
};function restoreIpAddresses(s) {
const n = s.length;
const out = [];
if (n < 4 || n > 12) return out;
const parts = [];
const dfs = (start) => {
const left = 4 - parts.length;
if (left === 0) {
if (start === n) out.push(parts.join("."));
return;
}
if (n - start < left || n - start > 3 * left) return;
let val = 0;
for (let len = 1; len <= 3 && start + len <= n; len++) {
if (len > 1 && s[start] === '0') break;
val = val * 10 + (s.charCodeAt(start + len - 1) - 48);
if (val > 255) break;
parts.push(s.substring(start, start + len));
dfs(start + len);
parts.pop();
}
};
dfs(0);
return out;
}Edge cases to test
- Fewer than 4 or more than 12 digits: no answer
- Zeros: "0" is a valid part, but "01" or "00" are not
- Parts above 255, like "256"
- A string of all zeros, like "0000"
Hints
Hint 1
An address has exactly four parts, each one to three digits long. How many ways can you place three dots?
Hint 2
A part is valid when it is "0" or starts with a non-zero digit, and its value is at most 255.
Hint 3
Build the parts left to right and stop early when the digits left cannot fill the remaining parts.
FAQ
What is the best time complexity for Restore IP Addresses?
Optimal (backtracking with pruning) runs in O(1) time and O(1) extra space. The recursion tree has at most 3⁴ = 81 leaves, and pruning cuts most of them.
Which pattern does Restore IP Addresses use?
It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Letter Combinations of a Phone Number, Confusing Number II, Strobogrammatic Number II.
Is there a brute force solution for Restore IP Addresses?
Yes. Brute force (try every dot placement) takes O(1) time and O(1) space. Choose the lengths of the first three parts (each 1 to 3); the fourth part is whatever remains.
Which edge cases should I test for Restore IP Addresses?
Fewer than 4 or more than 12 digits: no answer; Zeros: "0" is a valid part, but "01" or "00" are not; Parts above 255, like "256"; A string of all zeros, like "0000".