Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Java: Real-World Examples

Restore IP Addresses

Explore how to restore all valid IP addresses from a string of digits by applying backtracking and constrained programming techniques. Understand how to efficiently place dots to form valid IP segments and use recursion to handle invalid cases. This lesson helps you implement a well-optimized algorithm for generating IP addresses from input strings, enhancing your problem-solving skills for coding interviews.

We'll cover the following...

Description

Given a string s containing only digits, you have to return all the possible IP addresses that can be obtained from the string s in a list.

The order in which IP addresses are placed in the list is not important.

A valid IP address consists of four integers, where each integer lies within the range of 0 and 255. These integers are separated by single dots . and cannot have leading zeros.

Constraints

  • The input string s consists of digits only.
  • 4 <= s.length <= 12

Let’s review a few examples below:

Coding exercise

Java
class Solution {
  public static List<String> restoreIpAddresses(String s) {
    // Write code here
    return new ArrayList<String>();
  }
}
Restore IP addresses

Solution

The naive brute force solution would be to check all possible positions of the dots and only keep the valid ones. We have 11 possible positions where we can place the dots. For the first dot ., we will have 11 possible positions, 10 for the second dot, and 9 for the third. Hence, in the worst case, we will have to perform 11×10×9=99011 \times 10 \times 9 = 990 ...