Solution: Restore IP Addresses

Statement

A valid IP address consists of four numeric segments separated by single dots. Each segment must be an integer between 0 and 255 (inclusive), and leading zeros are not allowed unless the segment is exactly ‘0.”

For instance, “10.0.1.25” and “172.16.0.5” are valid IP addresses, while “01.200.100.3,” “256.100.50.25,” and “172.16.0.500” are invalid.

Given a string s made up of digits only, return all possible valid IP addresses that can be created by inserting exactly three dots into the string. You cannot rearrange or delete any digits. The resulting list of valid IP addresses can be returned in any order.

Constraints:

• The input string s consists of digits only.

• $4 \leq$ s.length $\leq 12$

Naive approach

The naive approach would be to check all possible positions of the dots. Because an IP address requires inserting three dots, and if the input string contains $12$ digits, then there are $11$ possible positions between the digits where a dot can be placed. So, we initially have $11$ choices for the first dot, then $10$ choices for the second dot, and $9$ choices for the third dot. This results in at most $11 × 10 × 9 = 990$ combinations to validate in the worst case.

We can introduce three nested loops to try all possible positions for placing the dots: the outer loop iterates through every valid position for the first dot (up to position 11), the middle loop tries all possible positions for the second dot that come after the first, and the inner loop attempts every possible position for the third dot following the second. After placing the dots, each resulting substring between the dots must be validated as a valid number, meaning it should be between 0 and 255 (inclusive) and must not have leading zeros.

Overall, this approach has a time complexity of $O(n^3)$ due to the three nested loops required to place the dots. The space complexity is $O(1)$, since we are not using any additional data structures beyond a constant amount of space.

Optimized approach using backtracking

Each numeric segment in the IP address is known as an octet, and each octet can have 1 to 3 digits.

Example IP Address: $192.168.0.1$