Restore IP Addresses - Solution & Explanation

Problem Overview: Given a string containing only digits, generate all possible valid IPv4 addresses by inserting three dots. Each address must contain exactly four segments, and each segment must be between 0 and 255 without leading zeros (except the number 0 itself).

Approach 1: Backtracking (O(n^3) time, O(1) extra space)

This approach builds the IP address segment by segment using backtracking. Start from the first character and try to take 1, 2, or 3 digits as the next segment. After selecting a segment, validate it: the integer must be ≤255 and must not contain leading zeros like "01". If the segment is valid, recursively continue building the next part until four segments are formed.

The recursion stops when either four segments are created or the string is fully consumed. If both conditions match simultaneously, join the segments using dots and add the result to the output. Because each segment can only be length 1–3 and there are exactly four segments, the search space is small. This method systematically explores combinations while pruning invalid branches early.

This solution heavily relies on string slicing and validation checks. Interviewers expect candidates to reason about constraints such as segment length, leading zeros, and numeric bounds. The recursion depth is at most four, so auxiliary space remains constant aside from the output list.

Approach 2: Iterative Split Enumeration (O(n^3) time, O(1) extra space)

An alternative approach avoids recursion and instead enumerates all possible ways to place three dots using nested loops. Use three indices i, j, and k to represent split points in the string. These indices define four segments: s[0:i], s[i:j], s[j:k], and s[k:n]. Each segment must be length 1–3, so the loops only explore valid boundaries.

For every split combination, validate the four segments individually. Convert each substring to an integer and check the constraints: value ≤255 and no leading zeros unless the segment is exactly "0". If all segments pass validation, combine them into a dotted string and add it to the result list.

This method performs explicit enumeration instead of recursion, which some developers find easier to reason about during debugging. It still relies on careful string manipulation and boundary checks.

Recommended for interviews: The backtracking solution is the expected answer. It demonstrates control over recursive state exploration and pruning invalid candidates early. The iterative split method also works and shows strong reasoning about segment boundaries, but backtracking better reflects the pattern interviewers associate with constrained combinatorial generation problems.