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
- Backtrack over the four segments, each of length 1 to 3.
- Prune a segment with a leading zero (unless it is a single
"0") and any segment exceeding 255. - The recursion succeeds only when exactly four segments are used and the whole string is consumed.
- 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 == ncheck: a string like"1111"with four parts would be accepted even if characters remained. - Using
continueinstead ofbreakfor the 255 check: the array is not sorted, but segment length increases left to right, so longer parts are larger --breakis 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.