This problem requires generating all valid IP addresses by inserting three dots into a string of digits. The main challenge is pruning invalid segments early to prevent unnecessary recursion, particularly when segments exceed 255 or have leading zeros. A backtracking approach systematically explores segment placements while maintaining validity constraints, ensuring each candidate solution meets IP address rules.
Problem Statement
Given a string s containing only digits, generate all possible valid IP addresses by inserting three dots to split it into four integers. Each integer must be between 0 and 255 inclusive and cannot have leading zeros. You must preserve the original order of digits and cannot remove any character.
Return all valid IP addresses in any order. For example, given s = "25525511135", the valid outputs are ["255.255.11.135","255.255.111.35"]. The string length is at least 1 and at most 20.
Examples
Example 1
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Example details omitted.
Example 2
Input: s = "0000"
Output: ["0.0.0.0"]
Example details omitted.
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"]
Example details omitted.
Constraints
- 1 <= s.length <= 20
- s consists of digits only.
Solution Approach
Use Backtracking with Pruning
Start from the first character and recursively try to place dots after 1 to 3 digits. If a segment exceeds 255 or has leading zeros, prune that path immediately to avoid invalid addresses.
Track Current Segments and Position
Maintain a list of current segments and the current index in the string. When four segments are formed, check if the entire string has been consumed to validate a complete IP address.
Aggregate Valid Addresses
Once a valid combination of four segments is found, join them with dots and add to the result list. Continue backtracking to explore other possibilities until all options are exhausted.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(M ^ N \cdot N) |
| Space | O(M \cdot N) |
Time complexity is O(M ^ N \cdot N), where M is the maximum segment length (3) and N is the string length, due to recursive exploration. Space complexity is O(M \cdot N) for the recursion stack and temporary segment storage.
What Interviewers Usually Probe
- Expect candidates to handle leading zeros correctly and prune invalid paths.
- Look for efficient recursive or iterative backtracking rather than brute-force splitting.
- Watch if candidate avoids unnecessary string copying and joins segments carefully.
Common Pitfalls or Variants
Common pitfalls
- Not pruning segments larger than 255 leads to TLE.
- Allowing leading zeros in multi-digit segments generates invalid addresses.
- Incorrectly handling string bounds when placing dots can cause out-of-range errors.
Follow-up variants
- Return only the first k valid IP addresses instead of all.
- Count the total number of valid IP addresses without listing them.
- Generate IP addresses for a string that may contain non-digit separators, ignoring them in validation.
How GhostInterview Helps
- Highlights the correct backtracking pattern and pruning conditions step by step.
- Provides structured tracking of segment positions and recursion depth for correctness verification.
- Ensures candidates avoid common mistakes with leading zeros and segment validation automatically.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the best approach to solve Restore IP Addresses?
Use backtracking with pruning, trying segments of length 1 to 3 and discarding invalid ones immediately.
How do you handle leading zeros in Restore IP Addresses?
A segment with multiple digits cannot start with '0'; only single-digit '0' is valid.
What is the time complexity for this problem?
The time complexity is O(M ^ N \cdot N) due to recursive exploration of segments, with M being 3 and N the string length.
Can this problem be solved iteratively instead of recursively?
Yes, but iterative solutions typically simulate the backtracking process with explicit stacks, which can be more complex.
Why is pruning important in Restore IP Addresses?
Pruning prevents exploring invalid segments, reducing unnecessary recursion and improving efficiency.
Need direct help with Restore IP Addresses instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Restore IP Addresses from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve Word Search with backtracking by exploring adjacent cells to match a target word in a grid.
Open problem page#126 Word Ladder IIFind all shortest transformation sequences from beginWord to endWord using a dictionary, leveraging backtracking search with pruning for efficiency.
Open problem page#131 Palindrome PartitioningFind all possible palindrome partitioning of a string using backtracking and dynamic programming.
Open problem page