Restore Ip Addresses

Problem Description

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting three dots into s.

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros (e.g., “01” is invalid, but “0” is valid).

For example, given s = "25525511135", the valid IP addresses are ["255.255.11.135"].

Solution Approach

This problem can be solved using a backtracking approach. We need to split the string into four valid parts. A “valid part” is a number between 0 and 255, without any leading zeros unless the number is just “0”.

The core idea is to use a recursive helper function, say backtrack(start_index, path), where start_index is the current position in the input string s, and path is a list of the IP address parts we have found so far.

The base cases for the recursion are:

1. If we have found 4 parts (len(path) == 4) and we have consumed the entire string (start_index == len(s)), we have found a valid IP address. We join the parts with dots and add it to our results.
2. If we have found 4 parts but haven’t consumed the string, or if we have consumed the string but have fewer than 4 parts, we have reached an invalid state, so we backtrack.

In the recursive step, we try to form the next part of the IP address by taking a substring of length 1, 2, or 3 starting from start_index. For each potential part, we check if it’s valid:

1. The substring must not have leading zeros (unless it’s just “0”).
2. The integer value of the substring must be between 0 and 255.

If the part is valid, we add it to our current path and make a recursive call with an updated start_index. After the recursive call returns, we remove the part from the path to explore other possibilities (this is the “backtracking” step).

Since an IP address has a fixed structure (4 parts, with each part being at most 3 digits), the length of the input string s that can form a valid IP is limited (4 to 12 characters). This means the recursion depth and branching factor are small and constant, leading to a constant time complexity.

Complexity Analysis

• Time: O(1). The length of a valid IP address string is bounded between 4 and 12 characters. The backtracking algorithm has a fixed recursion depth (at most 4 levels) and a fixed branching factor (at most 3 branches for lengths 1, 2, 3). Therefore, the total number of explorations is constant, regardless of the input string length (within the valid range).
• Space: O(1). The recursion stack depth is at most 4. The path list stores at most 4 parts. The space required for the result list is not typically counted for space complexity, but even if it were, the number of possible valid IP addresses is bounded.

Notes & Learnings

• This is a classic example of a backtracking problem where we need to find all valid combinations by partitioning a string.
• Careful handling of constraints is key: checking for leading zeros, the 0-255 range, and the final length of the path and consumed string.
• Pruning the search space is important for efficiency. For instance, we can stop early if the remaining characters are too many or too few to form the remaining parts of the IP address. My solution does this implicitly. For example, if start_index + length > n: stops us going out of bounds.