Solution: Restore IP Addresses
Explore how to restore valid IP addresses from a string of digits by applying a backtracking method. Understand the constraints for IP segments, recursive placement of dots, and how to prune invalid paths. This lesson helps you implement an optimized solution that generates all valid IP addresses by considering each segment’s numerical and structural rules.
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
sconsists of digits only.s.length
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