Reference: LeetCode EPI 6.9
Difficulty: Medium

## Problem

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

## Analysis

### Backtracking

The build consists of numbers of each part in an address. It is at most of size $4$. So the base case of the recursive function is when build.size() equals $4$. In terms of whether we should concatenate each part and put it in the result list, we should check if the depth d has reached its end s.length(). If yes, it is a valid address; if no, there are still some elements left and we can’t say it is a valid address.

As for the main part of the recursive function, we should at most consider three characters in the string: d + 0, d + 1, d + 2. But notice that if the first character is 0, then we should not consider the following characters that give 00, 01, 001. All of these combinations are invalid.

To write succinct code, we can first check if the first character is $0$ and then we know whether we should consider $1$ character (0 itself) or $3$ characters as usual (eg. 123). Before backtracking, check if the part we have constructed is valid.

Time: $O(1)$
Space: $O(1)$

### Iteration

We use three loops to express the idea. Before we need a function to determine if a string is a valid part of an address.

If the length of the string does not satisfy, return false. If the string starts with $0$, we should not consider cases such as 00, 000, etc. We only allow 0 to be in a part. Finally, check the value of the string if it is in [0, 255].

In each loop, we consider strings first, second, third and fourth. The first three strings can be enumerated in three times. For example, first can only be the first three characters in the string.

Note: Remember to check the upper bound index for substring. It should not be greater than n.

Time: $O(1)$
Space: $O(1)$

Comment
Junhao Wang
a software engineering cat