Restore IP Addresses
Asked at Oracle
Problem
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. A valid IP address consists of exactly four integers separated by single dots, where each integer is between 0 and 255.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | MEDIUM | View all Oracle questions → |
How to Think About It
Brute force: try every possible way to split s into 4 non-empty parts.
Use backtracking to build each octet one at a time.
Prune branches where the current octet exceeds 255 or has leading zeros.
At each step, try taking 1, 2, or 3 characters for the current octet.
When 4 octets are formed and all of s is consumed, add the result.
Optimal Approach
Use backtracking to try placing 1, 2, or 3 digits for each of the four octets. At each step, extract the substring, validate it (no leading zeros, value 0-255), and recurse for the next octet. When four valid octets are placed and no characters remain, add the IP to the result. The maximum recursion depth is 4 and each level branches at most 3 ways, giving O(1) effective time with string operations dominating at O(n).
What Trips People Up in Real Interviews
Clarify edge cases: leading zeros (only "0" is valid), empty segments.
Mention pruning strategies to avoid unnecessary recursion.
Explain why at most 3 digits per octet bounds the recursion.
Discuss that the result set is small so backtracking is efficient.
Ask if duplicates need to be handled (input guarantees no ambiguity).
Solution Code
def restoreIpAddresses(s):
result = []
def backtrack(start, parts):
if len(parts) == 4:
if start == len(s):
result.append('.'.join(parts))
return
for length in range(1, 4):
if start + length > len(s):
break
segment = s[start:start + length]
if len(segment) > 1 and segment[0] == '0':
break
if int(segment) > 255:
break
backtrack(start + length, parts + [segment])
backtrack(0, [])
return resultFrequently Asked Questions
What is the Restore IP Addresses problem?
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. A valid IP address consists of exactly four integers separated by single dots, where each integer is between 0 and 255.
How do you solve Restore IP Addresses?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Restore IP Addresses?
Restore IP Addresses is asked at Oracle. It is a medium difficulty problem.
What are common mistakes on Restore IP Addresses?
- Clarify edge cases: leading zeros (only "0" is valid), empty segments.
- Mention pruning strategies to avoid unnecessary recursion.
- Explain why at most 3 digits per octet bounds the recursion.
- Discuss that the result set is small so backtracking is efficient.
- Ask if duplicates need to be handled (input guarantees no ambiguity).