Restore IP Addresses
Explore how to apply backtracking to solve the problem of restoring valid IP addresses from a continuous string of digits. This lesson helps you understand segment validation, proper dot placement, and efficient pruning techniques to generate all valid combinations.
We'll cover the following...
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
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
What is the correct output if the following string is given as input?
IP address = “00000000”
[“000.000.00”, “00.000.000”, “000.00.000”, “0.0.000.000”, “0.00.00.000”]
[“000.000.00”]
[“00.00.00.00”]
None
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Note: As an additional challenge, we have intentionally hidden the solution to this puzzle.
Try it yourself
Implement your solution in the following coding playground.
function restoreIpAddresses(s){// Replace this placeholder return statement with your codereturn []}export {restoreIpAddresses}