Restore Every Valid IP Address

Question

The question asks the candidate to restore every possible valid IP address from a given string of digits.

Codemia · Accepted Answer

To solve the problem of restoring valid IP addresses, we can use a backtracking approach. The main idea is to generate all possible combinations of segments of the IP address from the given string and check if each segment is valid. An IP address consists of four segments, each ranging from 0 to 255, and cannot have leading zeros unless the segment is '0' itself.

1. Initialize an empty list to store valid IP addresses.
2. Use a recursive function to explore all possible segmentations of the string.
3. In each recursive call, check if the current segment is valid:
   - It should be a number between 0 and 255.
   - It should not have leading zeros unless it is '0'.
4. If we have 4 valid segments and have consumed the entire string, add the constructed IP address to the list.
5. Return the list of valid IP addresses.

```python
def restore_ip_addresses(s):
    def is_valid(segment):
        return 0 <= int(segment) <= 255 and str(int(segment)) == segment

def backtrack(start=0, path=[]):
        if len(path) == 4:
            if start == len(s):
                result.append('.'.join(path))
            return
        for length in range(1, 4):
            if start + length <= len(s):
                segment = s[start:start + length]
                if is_valid(segment):
                    backtrack(start + length, path + [segment])

result = []
    backtrack()
    return result
```
This code defines a function that uses backtracking to find all valid IP addresses from a given string.

The time complexity of this solution is O(3^4) in the worst case, as we can have at most 4 segments, each of which can have a maximum of 3 digits. The space complexity is O(1) for the result list, as we are not using additional data structures that grow with input size.

Consider cases where the input string is too short or too long to form a valid IP address. For example, an empty string or a string with more than 12 digits should return an empty list. Additionally, handle cases with leading zeros carefully to ensure they do not create invalid segments.

Restore Every Valid IP Address

TikTok

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

TikTok Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string