93. Restore IP Addresses
Model: qwen3.5:9b
Topics: String,Backtracking
FAANG asked: 0
Acceptance rate: 37.9%
Problem Breakdown
We are given a string s containing only digits, and we need to reconstruct all possible valid IP addresses from this sequence of characters. A valid IP address has specific structural rules that must be strictly enforced during reconstruction.
Inputs:
- String
s: Contains 0–3000 digits (though practically limited by IP constraints).
Outputs:
- List of strings: Each string represents a unique, valid IPv4 address format derived from the input characters in order. No reordering or skipping is allowed; we must partition the original sequence exactly into four segments separated by dots.
Implicit Constraints & Edge Cases:
- Length Limitation: A standard IP segment (0–255) has a maximum of 3 digits. With 4 segments, the total length cannot exceed 12 characters. If
sis longer than 12, no solution exists immediately. - Leading Zeros: “0” is valid; “01”, “007” are invalid because they have leading zeros (unless it’s just a single zero).
- Value Range: Each segment must be an integer between 0 and 255 inclusive.
Intuition
Initially, one might think of brute-forcing every possible way to place three dots into the string s. However, since we know exactly how many segments (4) are required and each has a maximum length constraint (3), this is fundamentally a partitioning problem with constraints on sub-segments.
A naive approach would try inserting dots at every position between characters. If we do that blindly without checking validity of the resulting numbers or remaining string lengths, it becomes inefficient ( roughly).
The key insight here is Backtracking (Depth-First Search). We can build the IP address segment by segment from left to right. At each step:
- Try taking a substring of length 1, 2, or 3 starting at our current position.
- Validate that this specific substring forms an integer and has no leading zeros (unless it is exactly “0”).
- If valid, recurse to find the next segment.
We also need Pruning:
- We stop if we have formed all 4 segments but haven’t consumed the whole string.
- We stop if consuming a substring leaves fewer characters than needed for remaining segments (e.g., needing at least one digit per remaining slot).
- Crucially, since max valid length is 12, any input can be rejected immediately in constant time.
Approach
We will use a recursive helper function backtrack(start_index) to explore all valid partitions.
Algorithm Steps:
- Base Case: If we have collected exactly 4 segments and the current index equals the length of string
s, add this combination to our results list. - Recursive Step: Iterate through possible lengths for the next segment (
ifrom 0 to 3). This means taking a substring starting atstart_indexwith length up to 3 (since max value is 255, we can’t take more than 3 digits anyway).- Extract candidate string.
- Validation Check: Ensure the integer value of this segment . Also ensure no leading zeros exist unless the number itself is “0”.
- If valid, append to current path and recurse with
start_index + length.
- Backtracking Logic: After returning from recursion (or if invalid), remove the last added segment before trying other lengths for this position.
Optimization Note: Before starting backtracking, check len(s) < 4 or len(s) > 12. If so, return empty list immediately to avoid unnecessary computation on large inputs given in constraints ().
Complexity Analysis
- Time Complexity: where is the number of segments (fixed at 4), but practically bounded by string length. However, due to our early exit for
len(s) > 12, and since each segment has a max depth of 3 branches, this effectively runs in constant time relative to large inputs ( after initial check). For valid lengths (up to 12), the number of partitions is small. - Space Complexity: where is the length of
s, primarily for storing the result list and recursion stack depth (which is constant at max 4 levels).
Solution
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
# Optimization: Valid IP addresses have between 4 to 12 digits.
if len(s) < 4 or len(s) > 12:
return []
res = []
def backtrack(start_index):
# Base case: If we've formed exactly 4 segments and consumed the string, it's valid
if start_index == len(s):
# We need to track segment count.
# To avoid passing 'segments' state in closure complexity,
# let's use a simpler approach with explicit path tracking or global counter logic inside recursion.
pass
# Let's refine the structure for clarity and standard backtracking pattern:
def helper(start_index):
if len(res) > 0: return # Not needed here as we build res directly, but let's track segments count properly.
# Actually, cleaner to use a list `path` or pass segment count in recursion args
path = []
def dfs(idx, parts_count):
# If all 4 parts are formed and index reached end of string -> Valid IP found
if idx == len(s) and parts_count == 4:
res.append(".".join(path))
return
# Pruning: We need at least (4 - parts_count) characters remaining for the rest segments.
# Each segment needs min length 1. So we must have enough chars left.
if len(s) - idx < (4 - parts_count):
return
# Try lengths of 1, 2, or 3 digits for current part
for i in range(1, 4):
end = idx + i
# Pruning: Don't go out of bounds
if end > len(s): break
segment_str = s[idx:end]
# Check leading zero constraint (invalid unless "0")
if len(segment_str) > 1 and segment_str[0] == '0':
continue
val = int(segment_str)
if val <= 255:
path.append(segment_str)
dfs(end, parts_count + 1)
path.pop()
# Start DFS from index 0 with 0 segments formed so far
dfs(0, 0)
return res
Edge Cases Handled
- Empty String / Short Strings: The initial length check (
len(s) < 4) handles cases where the string is too short to form even one valid IP. - Long Strings: The
len(s) > 12check ensures we don’t waste time on inputs that physically cannot be IPs (since max digits for “0”-“9” per segment * 4 = 3*4=12). - Leading Zeros: Explicitly checked via
if len(segment_str) > 1 and segment_str[0] == '0'. This rejects inputs like “05”, but accepts “0”. - Value Overflow (>255): Checked by converting substring to integer (
int(segment_str) <= 255). Note that Python handles large integers automatically, so overflow isn’t an issue in the language sense, but logic-wise we must reject values > 255.