Domain 2MediumCORE

Restore IP Addresses

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String#Backtracking

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:

  1. 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 s is longer than 12, no solution exists immediately.
  2. Leading Zeros: “0” is valid; “01”, “007” are invalid because they have leading zeros (unless it’s just a single zero).
  3. 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 (O(N4)O(N^4) 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:

  1. Try taking a substring of length 1, 2, or 3 starting at our current position.
  2. Validate that this specific substring forms an integer ≤255\le 255 and has no leading zeros (unless it is exactly “0”).
  3. 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 >12> 12 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:

  1. 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.
  2. Recursive Step: Iterate through possible lengths for the next segment (i from 0 to 3). This means taking a substring starting at start_index with 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 ≤255\le 255. Also ensure no leading zeros exist unless the number itself is “0”.
    • If valid, append to current path and recurse with start_index + length.
  3. 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 (N≤3000N \le 3000).

Complexity Analysis

  • Time Complexity: O(4k)O(4^k) where kk 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 (O(1)O(1) after initial check). For valid lengths (up to 12), the number of partitions is small.
  • Space Complexity: O(N)O(N) where NN 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) > 12 check 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.