Do you think IIT Guwahati certified course can help you in your career?
Introduction
Today's problem Restore IP Addresses is a famous problem of the topic Recursion and Backtracking. If you are unaware of the significance of these topics, you can check them out at Backtracking.
In this article, we will see different approaches to solve this problem.
What is a valid IP address?
A valid IP address will consist of four integers separated by dots and cannot have leading zeros.
Note:
Each integer is between 0 to 255.
You can return the IP addresses in any order.
There should be four partitions of the given string.
Example
"0.098.783.234"," 180.26@.221.111"," 111.22.333" are invalid IP addresses due to the violation of the above rules.
Input: 25525511135
Output: "255.255.111.35"," 255.255.11.135"
In this example, as we can see that there are two variations of this string.
Suppose 255 is one block, 255 is another block, and so on, now one block can contain digits of range 0 - 255. So we have to divide our string accordingly.
Problem Statement
Given a string consisting of only digits, you have to return all the possible valid IP addresses.
Approach 1: Using Backtracking
We will be using Backtracking to solve this problem.
What can be the approach to solve this problem?
We will be dividing the string into four segments/blocks, and each block will be divided by following the rules.
i+1,i+2,i+3 are the positions for partition into segments. Now we can partition on i+2 only if it is not starting with '0'.
We can partition on i+3 only if it is not starting with '0' and is within the range 0-255.
There will be no condition for i+1. It can be a single '0', and it will definitely be in the range of 0-255.
As you can see, we are using the backtracking technique, So what will be the base condition here?
The base condition will be that 'i' should not exceed the length of the string, as well as the partitions, should be four.
import java.util.ArrayList;
import java.util.List;
public class IPaddress {
//Method for getting the valid IP address
public static List < String > restore(String s) {
List < String > list = new ArrayList < > ();
help(s, 0, 0, "", list);
return list;
}
//Method for dividing the string into segments
public static void help(String s, int i, int par, String ans, List < String > ret) {
if (i == s.length() || par == 4) {
if (s.length() == i && par == 4) {
ret.add(ans.substring(0, ans.length() - 1));
}
}
help(s, i + 1, par + 1, ans + s.charAt(i) + ".", ret);
if (i + 2 <= s.length() && isvalid(s.substring(i, i + 2)))
//substring method will provide you the subset of the string by defining the
//starting and ending indexes.
help(s, i + 2, par + 1, ans + s.substring(i, i + 2) + ".", ret);
if (i + 3 <= s.length() && isvalid(s.substring(i, i + 3)))
help(s, i + 3, par + 1, ans + s.substring(i, i + 3) + ".", ret);
}
//For checking out the given conditions
private static boolean isvalid(String str) {
if (str.charAt(0) == '0')
return false;
int val = Integer.parseInt(str);
return val <= 255;
}
public static void main(String[] args) {
System.out.println(
restore("0000").toString());
}
}
You can also try this code with Online Java Compiler
The next approach that we are going to discuss is by using DP. There are four parts of the IP. We begin iterating from the end of the string and work our way back to the beginning. We create a DP 2D array of size (4 x N). The DP array can only have two values: 1 (true) or 0 (false) (false). If we can build 1 portion of IP from the substring starting at I and ending at the end of the given string, there is a way in which we can use dp[0][i]. Similarly, dp[1][i] indicates whether two portions of IP can be created from the substring, starting at I and ending at the end of the string.
After the creation of dp array, we proceed to the creation of valid IP addresses. We'll begin at the 2D dp array's bottom left corner. We only iterate 12 times, but those will all be genuine IP addresses because we only form valid IP addresses.
Implementation
public static ArrayList < String > list;
//To store the IP addresses
public static ArrayList < String >
restore(String s) {
int n = s.length();
list = new ArrayList < > ();
if (n < 4 || n > 12)
return list;
//Creation of dp array for storing the values
int dp[][] = new int[4][n];
for (int i = 0; i < 4; i++) {
for (int j = n - 1; j >= 0; j--) {
if (i == 0) {
//Substring method will provide you the subset
//from the given string
String ans = s.substring(j);
if (isValid(ans)) {
dp[i][j] = 1;
} else if (j < n - 3) {
break;
}
} else {
if (j <= n - i) {
for (int k = 1; k <= 3 && j + k <= n; k++) {
String str = s.substring(j, j + k);
if (isValid(str)) {
if (j + k < n && dp[i - 1][j + k] == 1) {
dp[i][j] = 1;
break;
}
}
}
}
}
}
}
if (dp[3][0] == 0)
return list;
//help function
help(dp, 3, 0, s, "");
return list;
}
//dividing into segments
public static void help(int dp[][], int i, int c, String str, String ret) {
if (i == 0) {
ret += str.substring(c);
list.add(ret);
return;
}
for (int j = 1; j <= 3 && c + j < str.length(); j++) {
if (isValid(str.substring(c, c + j)) && dp[i - 1][c + j] == 1) {
help(dp, i - 1, c + j, s, ret + s.substring(c, c + j) + ".");
}
}
}
private static boolean isValid(String str) {
String A[] = str.split("[.]");
for (String s: A) {
int i = Integer.parseInt(s);
if (s.length() > 3 || i < 0 || i > 255) {
return false;
}
if (s.length() > 1 && i == 0)
return false;
if (s.length() > 1 && i != 0 &&
s.charAt(0) == '0')
return false;
}
return true;
}
//Main function
public static void main(String[] args) {
System.out.println(restore("23322211555").toString());
}
}
You can also try this code with Online Java Compiler
Time Complexity: The time complexity of this approach is O(n).
Space Complexity: The space complexity is O(n).
FAQ'S
What do you mean by a valid IP Address? Answer: Here a valid IP address means that a string is divided into 4 segments separated by dots; each segment cannot have the leading zeros, and the integers should be in the range of 0-255.
What is the difference between Backtracking and Dynamic Programming? Answer: DP is an algorithmic technique addressing an optimization problem by breaking it down into smaller subproblems and taking advantage of the fact that the best solution to the overall problem is determined by the optimal method to its subproblems. Backtracking is an algorithmic strategy for recursively solving problems by working to develop a solution incrementally, one piece at a time, and eliminating any solutions that do not satisfy the problem's constraints at any point in time.
Key Takeaways
This blog covered the various methods to restore the IP addresses and their complexities. For better understanding, we have written the code in Java.
7+ registered 
