Restore Valid Addresses by Splitting a Digit String

Question

The question asks the candidate to implement a solution that splits a given digit string into all possible valid IP addresses, ensuring that there are no leading zeros in any segment.

Codemia · Accepted Answer

To solve the problem of restoring valid IP addresses from a digit string, I will use a depth-first search (DFS) approach. The main idea is to recursively explore all possible ways to split the string into four segments, ensuring that each segment is a valid IP address segment.

1. Initialize a list to store valid IP addresses.
2. Define a recursive function that takes the current index in the string and the current segments formed.
3. If we have formed 4 segments and used the entire string, add the segments to the list.
4. For each segment, check if it is valid (length between 1 and 3, no leading zeros unless it is '0', and value between 0 and 255).
5. Recursively call the function for the next index after the current segment.

The time complexity of this approach is O(3^n) in the worst case, where n is the length of the input string. This is because each segment can take at most 3 digits. The space complexity is O(n) for the recursion stack.

```python
def restore_ip_addresses(s):
    res = []
    def is_valid(segment):
        return len(segment) == 1 or (segment[0] != '0' and 0 < int(segment) <= 255)

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

dfs(0, [])
    return res
```
This code defines a function that uses DFS to find all valid IP addresses.

Interviewers will be looking for clarity in your explanation of the approach, your ability to handle edge cases, and your coding style. They will also assess your understanding of the algorithm's complexity and how well you can optimize or adapt your solution to variations of the problem.

Restore Valid Addresses by Splitting a Digit String

ByteDance

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

ByteDance 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