Restore IP Addresses
Explore how to use backtracking to restore all valid IP addresses from a string of digits. Understand the constraints on segment values and leading zeros to correctly identify 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.
import java.util.*;public class Main{public static List<String> restoreIpAddresses(String s) {// Replace this placeholder return statement with your codereturn new ArrayList<String>();}}