⚡Flashcard Drill➔
NeetCode #499LC-93MediumBacktracking
← Back to All Problems

#499 · #93 · Restore IP Addresses(复原 IP 地址)

📌 Problem Statement & Constraints

A valid IP address consists of exactly four integers separated by dots, each between 0 and 255 with no leading zeros. Given a string s of digits, return all valid IP addresses obtainable by inserting dots. Constraints: 1 <= s.length <= 20.

💡 Core Algorithmic Approaches

  1. Backtrack over the four segments, each of length 1 to 3.
  2. Prune a segment with a leading zero (unless it is a single "0") and any segment exceeding 255.
  3. The recursion succeeds only when exactly four segments are used and the whole string is consumed.
  4. A useful pruning is to bound the remaining characters: each remaining segment needs 1 to 3 characters.

💻 Benchmark Python3 Implementation

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        n = len(s)

        def dfs(start: int, parts: List[str]) -> None:
            if len(parts) == 4:
                if start == n:             # all characters consumed
                    res.append(".".join(parts))
                return
            # each remaining segment takes 1..3 characters
            remaining_segments = 4 - len(parts)
            if n - start < remaining_segments or n - start > 3 * remaining_segments:
                return
            for end in range(start, min(start + 3, n)):
                part = s[start:end + 1]
                if len(part) > 1 and part[0] == "0":
                    break                  # leading zero -> longer parts also invalid
                if int(part) > 255:
                    break                  # longer parts are even larger
                parts.append(part)
                dfs(end + 1, parts)
                parts.pop()

        dfs(0, [])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(3^4) = O(1) in the number of segments, i.e. O(n) for the slicing.
💾 Space Complexity
O(1) for the recursion depth (4 levels).

⚠️ Interview Pitfalls & Follow-ups

  • Allowing leading zeros: "01" is not a valid segment.
  • Forgetting the start == n check: a string like "1111" with four parts would be accepted even if characters remained.
  • Using continue instead of break for the 255 check: the array is not sorted, but segment length increases left to right, so longer parts are larger -- break is correct and faster.
  • Omitting the length-bounds pruning: it avoids exploring hopeless branches.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems