Program to generate all possible valid IP addresses from given string
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
A valid IP address must be in the form of A.B.C.D, where A, B, C, and D are numbers from 0-255. The numbers cannot be 0 prefixed unless they are 0.
Input: 25525511135 Output: [“255.255.11.135”, “255.255.111.35”] Explanation: These are the only valid possible IP addresses. Input: "25505011535" Output:  Explanation: We cannot generate a valid IP address with this string.
First, we will place 3 dots in the given string and then try out all the possible combinations for the 3 dots.
Corner case for validity:
For string "25011255255" 25.011.255.255 is not valid as 011 is not valid. 22.214.171.124 is not valid either as you are not allowed to change the string. 250.11.255.255 is valid.
Approach: Split the string with ‘ . ‘ and then check for all corner cases. Before entering the loop, check the size of the string. Generate all the possible combinations using looping through the string. If IP is found to be valid then return the IP address, else simply return the empty list.
Below is the implementation of the above approach:
- Time Complexity: O(n^3), where n is the length of the string
Three nested traversal of the string is needed, where n is always less than 12.
- Auxiliary Space: O(n).
As as extra space is needed.
Another Efficient Approach (Dynamic Programming): There is a dp approach exist for this problem and can be solved in time complexity O(n*4*3)=O(12n)=O(n) and space complexity O(4n).
Approach: We know that there are only 4 parts of the IP. We start iterating from the end of string and goes to the start of string. We create a dp 2D-array of size (4 x N). There can be only 2 values in the dp array i.e. 1(true) or 0(false). dp[i] tells if we can create 1 part of IP from the substring starting from i to end of string. Similarly, dp[i] tells if we can create 2 parts of IP from the substring starting from i to end of string.
After creating the dp array, we start creating the valid IP addresses. We start from the bottom left corner of the 2D dp array. We only iterate 12 times(worst case) but those also will be the valid IP addresses because we only form valid IP addresses.
- Time Complexity: O(n), where n is the length of the string. The dp array creation would take O(4*n*3) = O(12n) = O(n). Valid IP creation from dp array would take O(n).
- Auxiliary Space: O(n). As dp array has extra space of size (4 x n). It means O(4n).
Last Updated on November 13, 2021 by admin