Problem Description

This problem asks you to restore all possible valid IP addresses from a string containing only digits.

A valid IP address must meet these criteria:

• Contains exactly four integers separated by dots
• Each integer is between 0 and 255 (inclusive)
• No integer can have leading zeros (except for the number 0 itself)

Given a string s that contains only digits, you need to find all possible ways to insert exactly three dots into the string to form valid IP addresses. You cannot reorder or remove any digits from the original string.

For example:

• Input: "25525511135"
• Possible outputs: ["255.255.11.135", "255.255.111.35"]

The solution uses a depth-first search (DFS) approach with backtracking. The dfs(i) function explores all possible ways to partition the string starting from index i. At each position, it tries to form segments of 1, 2, or 3 digits (since IP segments can't exceed 255, they can't be more than 3 digits long).

The check(i, j) helper function validates whether the substring from index i to j forms a valid IP segment by:

• Ensuring no leading zeros exist (unless the segment is just "0")
• Verifying the numeric value is between 0 and 255

The algorithm maintains a temporary list t to build the current IP address being explored. When exactly 4 valid segments are formed and all characters are used, the IP address is added to the answer list. The backtracking mechanism (using t.pop()) allows exploration of all possible combinations.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves string manipulation and generating valid IP addresses, not graph traversal with nodes and edges.

Need to solve for kth smallest/largest?

• No: We need to find all valid IP addresses, not the kth smallest or largest element.

Involves Linked Lists?

• No: The problem works with a string of digits, not linked list data structures.

Does the problem have small constraints?

• Yes: The constraints are relatively small - an IP address has exactly 4 segments, each segment can be at most 3 digits long (0-255), and the input string length is limited (maximum would be 12 digits for a valid IP like "255.255.255.255").

Brute force / Backtracking?

• Yes: We need to explore all possible ways to place 3 dots in the string to form 4 segments. This requires trying different combinations and backtracking when a path doesn't lead to a valid IP address.

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This makes sense because:

• We need to generate all possible valid combinations
• We have a clear constraint system (4 segments, each 0-255, no leading zeros)
• We need to explore different partitioning choices and undo them if they don't work
• The search space is manageable due to small constraints (at most 3 digits per segment)

Intuition

The key insight is that we need to place exactly 3 dots in a string of digits to create 4 segments. Each segment must be a valid IP address component (0-255 with no leading zeros).

Think of this problem as making decisions at each position: "Should I end the current segment here or continue adding digits to it?" Since each segment can have 1, 2, or 3 digits maximum, we have limited choices at each step.

The backtracking pattern emerges naturally because:

1. We're exploring all possible ways to partition the string
2. At each position, we try different segment lengths (1, 2, or 3 digits)
3. If a choice leads to an invalid IP segment, we need to undo it and try another option

For example, with string "25525511135":

• We could start with "2", "25", or "255" as the first segment
• Each choice leads to different possibilities for the remaining segments
• We need to systematically explore all these branches

The recursive structure becomes clear: at position i, we:

1. Try taking the next 1, 2, or 3 digits as a segment
2. Check if this forms a valid IP segment (0-255, no leading zeros)
3. If valid, recursively solve for the rest of the string
4. If we successfully form 4 segments using all digits, we found a valid IP
5. Backtrack by removing the current segment and trying the next possibility

This is a classic "generate all valid combinations" problem where backtracking shines - we build solutions incrementally, validate constraints at each step, and backtrack when we hit dead ends.

Learn more about Backtracking patterns.

Solution Approach

The solution implements a depth-first search (DFS) with backtracking to generate all valid IP addresses. Here's how the implementation works:

Main Components:

1. DFS Function dfs(i): This recursive function explores all possible ways to partition the string starting from index i.

2. Validation Function check(i, j): Validates whether substring s[i:j+1] forms a valid IP segment by:

   • Checking for leading zeros: s[i] == "0" and i != j returns False (single "0" is valid, but "01", "012" are not)
   • Verifying the numeric value is within range: 0 <= int(s[i : j + 1]) <= 255

Algorithm Flow:

1. Base Cases in DFS:

   • If i >= n and we have exactly 4 segments (len(t) == 4), we found a valid IP address - join segments with dots and add to answer
   • If i >= n or we already have 4 segments but haven't used all characters, this path is invalid - return

2. Recursive Case:

   • From current position i, try taking the next 1, 2, or 3 characters as a segment
   • Loop boundary is min(i + 3, n) to avoid going out of bounds
   • For each potential segment s[i:j+1]:
     • Use check(i, j) to validate it
     • If valid, add to temporary list t
     • Recursively call dfs(j + 1) to process remaining string
     • Backtrack by removing the segment with t.pop()

Data Structures:

• ans: List to store all valid IP addresses
• t: Temporary list acting as a stack to build current IP address being explored
• n: Length of input string for boundary checking

Example Walkthrough with "25525511135":

1. Start with i=0, try "2" (valid) → recurse with remaining "5525511135"
2. From "5525511135", try "5" (valid) → recurse with "525511135"
3. Continue this process, building segments like ["2", "5", "5", "25511135"] - invalid (last segment > 255)
4. Backtrack, try ["2", "5", "52", "5511135"] - invalid
5. Keep backtracking and exploring until finding valid combinations like ["255", "255", "11", "135"]

The backtracking ensures we explore all possible partitions systematically while pruning invalid paths early through the validation checks.

Example Walkthrough

Let's trace through the algorithm with input string "2552" to find all valid IP addresses.

Initial State:

• String: "2552" (length = 4)
• Need to form exactly 4 segments
• Starting at index i = 0
• Temporary list t = []

Step 1: First segment starting at index 0

• Try "2" (indices 0-0): Valid ✓ (0 ≤ 2 ≤ 255)
  • Add to t = ["2"]
  • Recurse with i = 1

Step 2: Second segment starting at index 1

• Try "5" (indices 1-1): Valid ✓
  • Add to t = ["2", "5"]
  • Recurse with i = 2

Step 3: Third segment starting at index 2

• Try "5" (indices 2-2): Valid ✓
  • Add to t = ["2", "5", "5"]
  • Recurse with i = 3

Step 4: Fourth segment starting at index 3

• Try "2" (indices 3-3): Valid ✓
  • Add to t = ["2", "5", "5", "2"]
  • Recurse with i = 4
  • Base case reached: i = 4 >= n and len(t) = 4
  • Found valid IP: "2.5.5.2" ✓
  • Backtrack: t.pop() → t = ["2", "5", "5"]

Step 5: Backtrack to explore other paths

• Back at index 2, try "52" (indices 2-3): Valid ✓
  • Add to t = ["2", "5", "52"]
  • Recurse with i = 4
  • Base case: i = 4 >= n but len(t) = 3 (need 4 segments)
  • Invalid path - return
  • Backtrack: t.pop() → t = ["2", "5"]

Step 6: Continue backtracking

• Back at index 1, try "55" (indices 1-2): Valid ✓
  • Add to t = ["2", "55"]
  • Recurse with i = 3
  • Try "2" (indices 3-3): Valid ✓
    • Add to t = ["2", "55", "2"]
    • Recurse with i = 4
    • Base case: i = 4 >= n but len(t) = 3 (need 4 segments)
    • Invalid path - return

Step 7: Try longer first segment

• Back at index 0, try "25" (indices 0-1): Valid ✓
  • Add to t = ["25"]
  • Continue exploring with remaining "52"...
  • This path won't yield valid IPs (can't form 4 segments from "52")

Step 8: Try even longer first segment

• Back at index 0, try "255" (indices 0-2): Valid ✓
  • Add to t = ["255"]
  • Only "2" remains - can't form 3 more segments
  • Invalid path

Final Result: Only one valid IP address found: ["2.5.5.2"]

The algorithm systematically explores all possible ways to partition the string into 4 segments, validates each segment (0-255, no leading zeros), and backtracks when a path becomes invalid. The key is trying segments of length 1, 2, and 3 at each position and using the temporary list t as a stack to build and unbuild potential solutions.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × 3^4) or simplified to O(n)

The algorithm uses backtracking to explore all valid IP address combinations. At each position, we try at most 3 different segment lengths (1, 2, or 3 digits). Since an IP address has exactly 4 segments, we make at most 3^4 = 81 recursive calls in the decision tree. For each valid combination, we perform string operations including:

• The check function which validates segments in O(1) time (checking leading zeros and integer conversion for at most 3 digits)
• String slicing s[i : j + 1] which takes O(segment_length) time, at most O(3)
• The join operation when forming the final IP address takes O(n) time

Therefore, the overall time complexity is O(3^4 × n) = O(n × 3^4) = O(n) since 3^4 is a constant.

Space Complexity: O(n)

The space complexity consists of:

• The recursion call stack depth which is at most 4 (for 4 segments of an IP address): O(4) = O(1)
• The temporary list t storing at most 4 segments, each with maximum length 3: O(4 × 3) = O(1)
• The ans list storing all valid IP addresses. In the worst case, each valid IP address is a string of length approximately n + 3 (original digits plus 3 dots): O(number_of_valid_IPs × n)
• Since the number of valid IPs is bounded by O(3^4) = O(1), the space for storing results is O(n)

The dominant factor is the space needed to store the output strings, giving us a total space complexity of O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Leading Zeros

One of the most common mistakes is incorrectly validating segments with leading zeros. Many developers forget that "0" by itself is valid, but "01", "001", "012" are not valid IP segments.

Incorrect Implementation:

def is_valid_segment(start, end):
    # Wrong: This rejects "0" as a valid segment
    if s[start] == "0" and end > start:
        return False
    # Or worse: forgetting this check entirely
    return 0 <= int(s[start:end+1]) <= 255

Correct Implementation:

def is_valid_segment(start, end):
    # Correct: Allow "0" but reject "01", "001", etc.
    if s[start] == "0" and start != end:  # start != end means multiple digits
        return False
    return 0 <= int(s[start:end+1]) <= 255

2. Off-by-One Errors in Index Management

Mixing up inclusive vs. exclusive indices when slicing strings or iterating through positions is a frequent source of bugs.

Common Mistakes:

# Wrong: Using exclusive end in validation but inclusive in slicing
for end_index in range(start_index, min(start_index + 3, string_length)):
    if is_valid_segment(start_index, end_index):
        # Inconsistent: using end_index instead of end_index + 1
        current_segments.append(s[start_index:end_index])  # Missing last character!
        backtrack(end_index)  # Should be end_index + 1

Solution: Be consistent with your indexing convention. If using inclusive end indices in validation, ensure slicing and recursion calls match:

for end_index in range(start_index, min(start_index + 3, string_length)):
    if is_valid_segment(start_index, end_index):
        current_segments.append(s[start_index:end_index + 1])  # +1 for slice
        backtrack(end_index + 1)  # +1 to start after current segment

3. Forgetting Edge Cases

Common Edge Cases Often Missed:

• Strings that are too short (less than 4 digits) or too long (more than 12 digits)
• Strings that can't form exactly 4 segments
• Strings with all zeros like "0000"

Solution: Add early validation:

def restoreIpAddresses(self, s: str) -> List[str]:
    # Early rejection for impossible cases
    if len(s) < 4 or len(s) > 12:
        return []
  
    # Rest of the implementation...

4. Not Properly Backtracking

Forgetting to remove elements from the temporary list after recursive calls leads to incorrect results.

Wrong:

def backtrack(start_index):
    # ... base cases ...
  
    for end_index in range(start_index, min(start_index + 3, string_length)):
        if is_valid_segment(start_index, end_index):
            current_segments.append(s[start_index:end_index + 1])
            backtrack(end_index + 1)
            # Forgot to pop! current_segments keeps growing incorrectly

Correct: Always pair append with pop:

current_segments.append(s[start_index:end_index + 1])
backtrack(end_index + 1)
current_segments.pop()  # Essential for proper backtracking