[Medium] 93. Restore IP Addresses

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

  • For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You may not reorder or remove any digits in s. You may return the valid IP addresses in any order.

Examples

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]

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"]

Constraints

  • 1 <= s.length <= 20
  • s consists of digits only.

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. IP address format: What is a valid IP address? (Assumption: Four parts separated by dots, each part is 0-255, no leading zeros except “0”)

  2. Restoration: What does “restore” mean? (Assumption: Insert dots to split string into four valid IP address parts)

  3. Return format: What should we return? (Assumption: List of all valid IP addresses - strings with dots inserted)

  4. Leading zeros: How should we handle leading zeros? (Assumption: Not allowed - “01” is invalid, “0” is valid)

  5. All combinations: Should we return all valid IPs? (Assumption: Yes - return all possible valid IP addresses)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Try all possible ways to insert three dots into the string. For each combination of three positions, split the string into four parts and check if each part is a valid IP segment (0-255, no leading zeros). This requires checking C(n-1, 3) combinations where n is string length, which is O(n³) combinations, each requiring validation. This works but is inefficient.

Step 2: Semi-Optimized Approach (7 minutes)

Use backtracking: try placing dots one at a time. For each dot position, validate the current segment before proceeding. If a segment is invalid, backtrack immediately. This prunes invalid branches early, reducing the search space significantly. However, the worst-case complexity is still exponential, though average case improves with pruning.

Step 3: Optimized Solution (8 minutes)

Use backtracking with careful validation. Place dots sequentially, ensuring each segment is valid (1-3 digits, 0-255, no leading zeros except “0”). Use early termination: if remaining characters cannot form valid segments (too few or too many), backtrack. Track the number of segments placed (need exactly 4). This achieves optimal time complexity by exploring only valid paths. The key optimizations are: validating segments immediately, checking if remaining string can form valid segments, and using backtracking to avoid exploring invalid combinations.

Solution: Backtracking with Python20 Optimizations

Time Complexity: O(1) - At most 3^4 = 81 combinations
Space Complexity: O(1) - At most 19 characters per IP address

This solution uses backtracking to try all possible ways to split the string into 4 parts. We optimize with Python20 features including string_view for efficient substring operations and early pruning.

Solution 1: Optimized Python20 Version

using namespace std
class Solution:
# Check if a segment is valid using string_view for efficiency
def isValid(self, segment):
    len = segment.length()
    # Single digit is always valid (0-9)
    if (len == 1) return True
    # Leading zero is invalid
    if (segment[0] == '0') return False
    # Check if <= 255 using efficient comparison
    if (len == 2) return True  // 10-99
    if len == 3:
        # Compare with "255" lexicographically
        return segment <= "255"
    return False  # len > 3 is invalid
void backtrack(
string_view s,
start,
list[int> dots,
list[str> result
) :
remainingLen = (int)s.length() - start
remainingCnt = 4 - (int)len(dots)
# Early pruning: check if remaining digits can form valid segments
if remainingLen > remainingCnt * 3  or  remainingLen < remainingCnt:
    return
# Base case: we have 3 dots, check if remaining segment is valid
if len(dots) == 3:
    lastSegment = s.substr(start)
    if isValid(lastSegment):
        # Build IP address efficiently
        str ip
        ip.reserve(s.length() + 3)  # Reserve space for dots
        last = 0
        for dot in dots:
            ip.append(s.substr(last, dot))
            last += dot
            ip.append(".")
        ip.append(s.substr(start))
        result.append(move(ip))
    return
# Try segments of length 1, 2, or 3
for (curr = 1 curr <= 3  and  curr <= remainingLen curr += 1) :
dots.append(curr)
segment = s.substr(start, curr)
if isValid(segment):
    backtrack(s, start + curr, dots, result)
dots.pop()
def restoreIpAddresses(self, s):
    list[int> dots
    dots.reserve(3)  # At most 3 dots
    list[str> result
    # Use string_view to avoid copying
    string_view sv(s)
    backtrack(sv, 0, dots, result)
    return result

Solution 2: Further Optimized with String Building

using namespace std
class Solution:
def isValid(self, segment):
    len = segment.length()
    if (len == 1) return True
    if (segment[0] == '0') return False
    if (len == 2) return True
    return len == 3  and  segment <= "255"
void backtrack(
string_view s,
start,
list[int> segments,
list[str> result
) :
remainingLen = (int)s.length() - start
remainingCnt = 4 - (int)len(segments)
if remainingLen > remainingCnt * 3  or  remainingLen < remainingCnt:
    return
if len(segments) == 3:
    lastSegment = s.substr(start)
    if isValid(lastSegment):
        # Build IP more efficiently by pre-calculating size
        str ip
        totalLen = (int)s.length() + 3
        ip.reserve(totalLen)
        pos = 0
        for segLen in segments:
            ip.append(s.substr(pos, segLen))
            pos += segLen
            ip += '.'
        ip.append(s.substr(start))
        result.append(move(ip))
    return
for (len = 1 len <= 3  and  len <= remainingLen len += 1) :
segments.append(len)
if isValid(s.substr(start, len)):
    backtrack(s, start + len, segments, result)
segments.pop()
def restoreIpAddresses(self, s):
    list[int> segments
    segments.reserve(3)
    list[str> result
    backtrack(string_view(s), 0, segments, result)
    return result

Key Optimizations (Python20)

  1. string_view: Avoids string copying when checking segments and building results
  2. reserve(): Pre-allocates memory for vectors and strings to avoid reallocations
  3. Early Pruning: Checks if remaining digits can form valid segments before recursing
  4. Move Semantics: Uses move() when pushing to result vector
  5. Efficient String Building: Pre-calculates size and uses append() for better performance

How the Algorithm Works

Step-by-Step Example: s = "25525511135"

  1. Try first segment “2” (length 1)
    • Valid: 2 (0-255)
    • Recursively try remaining: "5525511135"
  2. Try second segment “5” (length 1)
    • Valid: 5
    • Continue: "525511135"
  3. Continue building…
    • Eventually find: "255.255.11.135" and "255.255.111.35"

Visual Representation

"25525511135"
│
├─ "2" (valid)
│  ├─ "5" (valid)
│  │  ├─ "5" (valid)
│  │  │  └─ "25511135" → try "255", "2551", "25511"...
│  │  └─ "55" (valid)
│  │     └─ ...
│  └─ "55" (valid)
│     └─ ...
└─ "25" (valid)
   └─ ...

Algorithm Breakdown

1. Validation Function

def isValid(self, segment):
    if (segment.length() == 1) return True  // 0-9
    if (segment[0] == '0') return False     # Leading zero
    if (segment.length() == 2) return True  // 10-99
    return segment <= "255"                  // 100-255

2. Backtracking Function

def backtrack(self, s, start, segments, ...):
    # Early pruning
    if remainingLen > remainingCnt * 3  or  remainingLen < remainingCnt:
        return
    # Base case: 3 segments placed
    if len(segments) == 3:
        # Check last segment and build IP
    # Try segments of length 1, 2, 3
    for (len = 1 len <= 3 len += 1) :
    if isValid(s.substr(start, len)):
        backtrack(s, start + len, segments, result)

Complexity Analysis

Aspect Complexity
Time O(1) - At most 3^4 = 81 combinations
Space O(1) - At most 19 characters per IP address
Recursion Depth O(4) - Maximum 4 segments

Edge Cases

  1. All zeros: "0000" → ["0.0.0.0"]
  2. Leading zeros: "010010" → ["0.10.0.10","0.100.1.0"]
  3. Long string: "255255255255" → ["255.255.255.255"]
  4. Short string: "1111" → ["1.1.1.1"]

Why This Solution is Optimal

  1. Early Pruning: Eliminates invalid branches immediately
  2. String View: Avoids unnecessary string copies
  3. Memory Pre-allocation: Reduces reallocations
  4. Constant Time: Bounded by maximum 81 combinations
  5. Clean Backtracking: Simple and maintainable

Common Mistakes

  1. Not checking leading zeros: "010" is invalid
  2. Not checking range: Numbers must be 0-255
  3. Not pruning early: Should check remaining length
  4. String copying: Use string_view for efficiency
  5. Forgetting base case: Must have exactly 4 segments