Restore IP Addresses
Explore how to use backtracking to restore all possible valid IP addresses from a string of digits. Understand the constraints on segments, and practice implementing a solution that inserts exactly three dots without rearranging digits, preparing you for combinatorial coding challenges.
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.
vector<string> RestoreIpAddresses(string s){// Replace this placeholder return statement with your codereturn {};}