Restore IP Addresses — Solution in Python, Java & C++
Restore IP Addresses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Restore IP Addresses is a medium coding problem on strings and backtracking, asked in Amazon, Microsoft, Yahoo and Oracle interviews.
- Difficulty: Medium
- Topics: Strings, Backtracking
- Asked at: Amazon, Microsoft, Yahoo, Oracle
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An IPv4 address is four integers between 0 and 255 joined by dots, where no part has a leading zero: 10.0.1.255 is valid, while 10.01.1.2, 256.1.1.1 and 1.2.3 are not.
You are given a string s of digits. Insert exactly three dots into s — without removing, reordering or adding any digit — and return every valid IPv4 address that can be formed.
Return the addresses sorted in ascending lexicographic order (plain character comparison, where . comes before every digit). Return an empty list if none can be formed.
Example 1
Input: s = "10203"
Output: ["1.0.20.3","10.2.0.3"]
Explanation: `10.20.3` needs a fourth part, and `1.02.0.3` has a leading zero.
Example 2
Input: s = "0000"
Output: ["0.0.0.0"]
Example 3
Input: s = "1111111111111"
Output: []
Explanation: Thirteen digits cannot fit into four parts of at most three digits.
Constraints
1 <= s.length <= 20s consists of digits only
Hints for Restore IP Addresses
Hint 1
Every part has length 1, 2 or 3, so there are at most 3^3 ways to place the 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
Backtrack over the part lengths, pruning when the remaining digits cannot fill the remaining parts (fewer than one or more than three each).
How to solve Restore IP Addresses
Choose the four part lengths by backtracking; each choice is checked locally (no leading zero, value ≤ 255), and the remaining length bounds prune hopeless branches early.
Approach
- Recurse with the index
startof the next unread digit and the parts chosen so far. - When four parts are chosen, record
parts.join(".")ifstartreached the end ofs. - Otherwise, with
leftparts still to place andremdigits unread, stop ifrem < leftorrem > 3·left. - Try lengths 1, 2, 3 in that order: stop extending once the part would start with
0and be longer than one digit, or once its value exceeds 255 — both conditions only get worse with more digits. - Trying shorter parts first emits the addresses already in lexicographic order.
Why it works
Every address corresponds to exactly one choice of four lengths, and the search tries all choices that are not ruled out by a condition that would also rule out every extension, so nothing valid is missed and nothing is produced twice. The order is lexicographic because two addresses from the same digits first differ where one has a dot and the other a digit — the one with the shorter part there has the dot, and . sorts before digits; the search tries that shorter part first.
Complexity
- Time —
O(3^4 · n) — at most 81 leaves, each joined in O(n) - Space —
O(n) besides the output
Pitfalls
"0"is a valid part;"00"and"01"are not.- Strings longer than 12 digits (or shorter than 4) have no answer — the length bounds handle this without special cases.
- Comparing parts as strings (
"99" > "255") instead of numbers wrongly rejects valid parts.
Reference solution
Python
from typing import List
def restoreIpAddresses(s: str) -> List[str]:
res = []
parts = []
def dfs(start):
if len(parts) == 4:
if start == len(s):
res.append(".".join(parts))
return
left = 4 - len(parts)
rem = len(s) - start
if rem < left or rem > 3 * left:
return
for ln in range(1, 4):
if start + ln > len(s):
break
seg = s[start:start + ln]
if ln > 1 and seg[0] == "0":
break
if int(seg) > 255:
break
parts.append(seg)
dfs(start + ln)
parts.pop()
dfs(0)
return resJava
public static String[] restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
ipDfs(s, 0, new ArrayList<String>(), res);
return res.toArray(new String[0]);
}
static void ipDfs(String s, int start, List<String> parts, List<String> res) {
if (parts.size() == 4) {
if (start == s.length()) res.add(String.join(".", parts));
return;
}
int left = 4 - parts.size(), rem = s.length() - start;
if (rem < left || rem > 3 * left) return;
for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
String seg = s.substring(start, start + len);
if (len > 1 && seg.charAt(0) == '0') break;
if (Integer.parseInt(seg) > 255) break;
parts.add(seg);
ipDfs(s, start + len, parts, res);
parts.remove(parts.size() - 1);
}
}C++
void ipDfs(const string& s, int start, vector<string>& parts, vector<string>& res) {
if (parts.size() == 4) {
if (start == (int)s.size()) res.push_back(parts[0] + "." + parts[1] + "." + parts[2] + "." + parts[3]);
return;
}
int left = 4 - (int)parts.size(), rem = (int)s.size() - start;
if (rem < left || rem > 3 * left) return;
for (int len = 1; len <= 3 && start + len <= (int)s.size(); len++) {
string seg = s.substr(start, len);
if (len > 1 && seg[0] == '0') break;
if (stoi(seg) > 255) break;
parts.push_back(seg);
ipDfs(s, start + len, parts, res);
parts.pop_back();
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> res, parts;
ipDfs(s, 0, parts, res);
return res;
}JavaScript
var restoreIpAddresses = function(s) {
var res = [];
var parts = [];
var dfs = function(start) {
if (parts.length === 4) {
if (start === s.length) res.push(parts.join("."));
return;
}
var left = 4 - parts.length, rem = s.length - start;
if (rem < left || rem > 3 * left) return;
for (var len = 1; len <= 3 && start + len <= s.length; len++) {
var seg = s.substring(start, start + len);
if (len > 1 && seg[0] === "0") break;
if (parseInt(seg, 10) > 255) break;
parts.push(seg);
dfs(start + len);
parts.pop();
}
};
dfs(0);
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Backtracking