LeetCode 93: Restore IP Addresses Solution in Python Explained

Problem Statement

In LeetCode 93, you’re given a string s containing only digits. Your task is to return all possible valid IP addresses by splitting s into four integers (0-255), each represented as a string without leading zeros (except 0 itself), separated by dots. This differs from linked list tasks like LeetCode 92: Reverse Linked List II, focusing on string partitioning.

Constraints

• 1 <= s.length <= 20
• s contains only digits (0-9)

Example

Let’s see some cases:

Copy codeInput: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Explanation: Two valid splits: 255,255,11,135 and 255,255,111,35.

Copy codeInput: s = "0000"
Output: ["0.0.0.0"]
Explanation: Only one valid split: 0,0,0,0.

Copy codeInput: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Explanation: Five valid combinations.

These examples show we’re finding all valid four-part splits.

Understanding the Problem

How do you solve LeetCode 93: Restore IP Addresses in Python? Take s = "25525511135". We need ["255.255.11.135","255.255.111.35"]—each part must be 0-255, no leading zeros unless 0, and use all digits. This isn’t a decoding count like LeetCode 91: Decode Ways; it’s about generating valid partitions. We’ll use: 1. Backtracking: O(3⁴) time, O(1) space—our best solution. 2. Brute Force: O(3³) time, O(1) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Backtracking Approach (Primary)

Explanation

Backtracking explores all possible splits by building IP addresses part-by-part, checking validity (0-255, no leading zeros), and backtracking when a split fails. It’s the best solution due to its efficiency and ability to prune invalid paths early, keeping time complexity constant (since max parts = 4).

For s = "25525511135":

• Try 1-3 digits for each part.
• Build: "255", "255.255", "255.255.11", "255.255.11.135".
• Try next: "255.255.111.35".
• Stop when four parts use all digits.

Step-by-Step Example

Example 1: s = "25525511135"

Goal: Return ["255.255.11.135","255.255.111.35"].

• Start: result = [], parts = [].
• Step 1: Start at index 0, need 4 parts.
• "255" (valid), parts = ["255"], remain = "25511135".
• Next at index 3, need 3 parts.
• "255" (valid), parts = ["255","255"], remain = "11135".
• Next at 6, need 2 parts.
• "1" (valid), parts = ["255","255","1"], remain = "1135".
• "1135" (too long), backtrack.
• "11" (valid), parts = ["255","255","11"], remain = "135".
• "135" (valid), parts = ["255","255","11","135"], add "255.255.11.135".
• "111" (valid), parts = ["255","255","111"], remain = "35".
• "35" (valid), parts = ["255","255","111","35"], add "255.255.111.35".
• Finish: Return ["255.255.11.135","255.255.111.35"].

Example 2: s = "0000"

Goal: Return ["0.0.0.0"].

• Start: parts = [].
• Step 1: Index 0, need 4.
• "0" (valid), parts = ["0"], remain = "000".
• Index 1, need 3.
• "0" (valid), parts = ["0","0"], remain = "00".
• Index 2, need 2.
• "0" (valid), parts = ["0","0","0"], remain = "0".
• Index 3, need 1.
• "0" (valid), parts = ["0","0","0","0"], add "0.0.0.0".
• Finish: Return ["0.0.0.0"].

Example 3: s = "101023"

Goal: Return ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"].

• Start: Explore splits.
• Step 1: Index 0, need 4.
• "1" → "0" → "10" → "23".
• "1" → "0" → "102" → "3".
• "10" → "1" → "0" → "23".
• "10" → "10" → "2" → "3".
• "101" → "0" → "2" → "3".
• Finish: Return 5 valid IPs.

How the Code Works (Backtracking) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef restoreIpAddresses(s: str) -> list[str]:
    # Line 1: Initialize result list
    result = []
    # Stores all valid IP addresses (e.g., initially empty)

    # Line 2: Check length constraints
    if len(s) < 4 or len(s) > 12:
        # If string is too short (<4) or too long (>12), can’t form 4 parts of 1-3 digits
        return []

    # Line 3: Define backtracking helper function
    def backtrack(start: int, parts: list[str]):
        # start = current index in s, parts = current list of IP parts

        # Line 4: Base case - found 4 parts
        if len(parts) == 4:
            # If we have 4 parts (e.g., ["255","255","11","135"])
            if start == len(s):
                # If we’ve used all digits (start = len(s)), it’s a valid IP
                result.append('.'.join(parts))
                # Join parts with dots and add to result (e.g., "255.255.11.135")
            return

        # Line 5: Check if remaining length is feasible
        if len(s) - start > 3 * (4 - len(parts)):
            # If remaining digits exceed max possible (3 digits per remaining part), prune
            # e.g., 11 digits left, 2 parts needed (max 6) → impossible
            return

        # Line 6: Try 1-3 digit segments
        for length in range(1, 4):
            # Tries lengths 1, 2, 3 for the next part (e.g., "2", "25", "255")

            # Line 7: Check if segment length is possible
            if start + length > len(s):
                # If segment goes beyond string length, skip
                # e.g., start=10, length=3, len=11 → break
                break

            # Line 8: Extract segment
            segment = s[start:start + length]
            # Gets substring (e.g., start=0, length=3 → "255")

            # Line 9: Validate segment
            if (length > 1 and segment[0] == '0') or int(segment) > 255:
                # Invalid if: leading zero with >1 digit (e.g., "01") or > 255 (e.g., "256")
                continue

            # Line 10: Add segment and backtrack
            parts.append(segment)
            # Adds valid segment to parts (e.g., parts = ["255"])

            # Line 11: Recurse with next position
            backtrack(start + length, parts)
            # Moves to next segment (e.g., start=3, parts=["255"])

            # Line 12: Backtrack by removing segment
            parts.pop()
            # Removes segment to try next possibility (e.g., parts back to [])

    # Line 13: Start backtracking
    backtrack(0, [])
    # Begins at index 0 with empty parts list

    # Line 14: Return all valid IPs
    return result
    # Returns list of valid IP addresses (e.g., ["255.255.11.135", "255.255.111.35"])

This detailed explanation ensures the backtracking process is clear, efficiently finding all valid IPs.

Alternative: Brute Force Approach

Explanation

Generate all possible splits into four parts by trying every combination of 1-3 digits, validating each part (0-255, no leading zeros), and collecting valid IPs. Less efficient due to exhaustive checking but straightforward.

For "25525511135":

• Try all splits: 1-3 digits for each part.
• Validate and collect: "255.255.11.135", "255.255.111.35".

Step-by-Step Example (Alternative)

For "25525511135":

• Splits:
• 255,2,551,1135 (invalid).
• 255,255,11,135 (valid).
• 255,255,111,35 (valid).
• Finish: ["255.255.11.135","255.255.111.35"].

How the Code Works (Brute Force)

Copy codedef restoreIpAddressesBrute(s: str) -> list[str]:
    def is_valid(part: str) -> bool:
        return len(part) == 1 or (part[0] != '0' and int(part) <= 255)

    result = []
    n = len(s)
    if n < 4 or n > 12:
        return result

    for i in range(1, min(4, n-2)):
        for j in range(i+1, min(i+4, n-1)):
            for k in range(j+1, min(j+4, n)):
                p1, p2, p3, p4 = s[:i], s[i:j], s[j:k], s[k:]
                if all(is_valid(p) for p in [p1, p2, p3, p4]):
                    result.append(f"{p1}.{p2}.{p3}.{p4}")
    return result

Complexity

• Backtracking:
• Time: O(3⁴) – max 3 choices per 4 parts, constant due to constraints.
• Space: O(1) – excluding output, only parts list.
• Brute Force:
• Time: O(3³) – three nested loops, but less pruning.
• Space: O(1) – constant extra space.

Efficiency Notes

Backtracking is the best solution with O(3⁴) time (effectively constant for n ≤ 20), pruning invalid paths early—Brute Force is simpler but less efficient due to exhaustive splits.

Key Insights

• Backtracking: Prunes early.
• Validation: 0-255, no leading zeros.
• Four Parts: Fixed split requirement.

Additional Example

For s = "1111":

• Goal: ["1.1.1.1"].
• Backtracking: "1","1","1","1" → valid.

Edge Cases

• Too Short: "1" → [].
• Too Long: "1234567890123" → [].
• All Zeros: "0000" → ["0.0.0.0"].

Both solutions handle these well.

Final Thoughts

LeetCode 93: Restore IP Addresses in Python is a clever string partitioning challenge. The Backtracking solution excels with efficiency and clarity, while Brute Force offers a straightforward alternative. Want more? Try LeetCode 91: Decode Ways for string decoding or LeetCode 90: Subsets II for combinatorics. Ready to practice? Solve LeetCode 93 on LeetCode with "25525511135", aiming for ["255.255.11.135","255.255.111.35"]—test your skills now!