A program to generate all possible valid IP addresses from a given string



A valid IP address must be in the form ABCD, where A, B, C and D are numbers from 0 to 255. Numbers cannot be prefixed with 0 unless they are 0.

Examples:

 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`ll put 3 dots on a given string and then try all possible combinations for 3 dots.
Corner case for reality:

 For string "25011255255" 25.011.255.255 is not valid as 011 is not valid. 25.11.255.255 is not valid either as you are not allowed to change the string. 250.11.255.255 is valid. 

Match:
Break the line with & # 39 ;. and then check all corner cases. Check the string size before entering the loop. Create all possible combinations by looping through the line. If the IP address is valid, return the IP address, otherwise just return an empty list.

Below is the implementation of the above approach:

C ++

// C ++ program for generating everything possible
/ / valid IP addresses from given string
# include & lt; bits / stdc ++. h & gt;

using namespace std;

 
// The function checks if the numbers are IP
// valid or not.

int is_valid (string ip)

{

// Separated by & quot;. & quot;

vector & lt ; string & gt; ips;

string ex = "" ;

for ( int i = 0; i & lt; ip.size (); i ++)

{

if (ip [i] == ` .` )

{

ips.push_back (ex);

ex = "" ;

}

else

  {

ex = ex + ip [i];

}

}

  ips. push_back (ex);

 

// Checking corner cases

  // cout & lt; & lt; ip & lt; & lt; endl;

for ( int i = 0; i & lt; ips.size (); i ++)

{

// cout & lt; & lt; ips [i] & lt; & lt; endl;

if (ips [i] .length () & gt; 3 || 

stoi (ips [i] ) & lt; 0 || 

stoi (ips [i]) & gt; 255)

return 0;

 

if (ips [i] .length () & gt; 1 & amp; & amp; 

  stoi (ips [i]) == 0)

  return 0;

 

if (ips [i] .length () & gt; 1 & amp; & amp; 

  stoi (ips [i])! = 0 & amp; & amp; 

  ips [i] [0] == `0` )

return 0;

}

return 1;

}

 
// The function converts the string to an IP address

void convert ( string ip)

{

int l = ip.length ();

 

// Check line size

  if (l & gt; 12 || l & lt; 4)

  {

cout & lt; & lt; "Not Valid IP Address" ;

}

 

  string check = ip;

vector & lt; string & gt; ans;

 

// Generate different combinations.

  for ( int i = 1; i & lt; l - 2; i ++)

{

  for ( int j = i + 1; j & lt; l - 1; j ++)

{

for ( int k = j + 1; k & lt; l; k ++)

  {

check = check.substr (0, k) + "."

check. substr (k, l - k + 2);

check = check.substr (0, j) + "."

check.substr (j, l - j + 3);

check = check.substr (0, i) + "."

check.substr (i, l - i + 4);

 

// cout & lt; & lt; check & lt; & lt; endl;

// Check the correct combination

if (is_valid (check))

{

ans.push_back (check);

std :: cout & lt; & lt; check & lt; & lt; `` ;

}

check = ip;

}

}

  }

}

 
// Driver code

int main ()

{

string A = "25525511135" ;

string B = "25505011535" ;

 

convert (A);

convert (B);

 

return 0;

}

 
// This code is provided by Harshit

Java

// Java program to generate everything possible
// valid IP addresses from a given string

import java.util. *;

 

class GFG {

  

  // Function for recovering IP addresses

public static ArrayList & lt; String & gt; restoreIpAddresses (String A) 

{

if (A.length () & lt; 3 || A.length () & gt; 12 )

return new ArrayList & lt; & gt; ();

return convert (A);

}

 

  private static ArrayList & lt; String & gt; convert (String s) 

{

ArrayList & lt; String & gt; l = 

new ArrayList & lt; & gt ; ();

int size = s.length ();

 

String snew = s;

 

for ( int i = 1 ; i & lt; size - 2

i ++)

  {

  for ( int j = i + 1

j & lt; size - 1 ; j ++) 

{

  for ( int k = j + 1

k & lt; size; k ++) 

{

snew = snew.substring ( 0 , k ) +

"." + snew.substring (k);

snew = snew.substring ( 0 , j) + 

" . " + snew.substring (j);

snew = snew.substring ( 0 , i) + 

" . " + snew.substring (i); 

 

if (isValid (snew))

  {

  l.add (snew);

}

snew = s;

}

}

  }

 

Collections.sort (l, new Comparator & lt; String & gt; () 

{

public int compare (String o1, String o2)

{

String a1 [] = o1.split ( " [.] " );

String a2 [] = o2.split ( " [.] " );

 

int result = - 1 ;

for ( int i = 0 ; i & lt; 4 & amp; & amp; 

result! = 0 ; i ++) 

{

result = a1 [i] .compareTo (a2 [i]);

}

return result;

}

});

return l;

 

}

  

  private static boolean isValid (String ip) 

{

String a [] = ip.split ( " [.] " );

for (String s: a ) {

int i = Integer .parseInt (s);

if (s.length ( ) & gt; 3 || i & lt; 0 || i & gt; 255

{

return false ;

}

if (s.length () & gt; 1 & amp; & amp; i == 0 )

return false ;

if (s.length ( ) & gt; 1 & amp; & amp; i! = 0 & amp; & amp;

s.charAt ( 0 ) == `0` )

return false ;

}

 

  return true ;

}

 
// Driver code

public static void main (String [] args) 

{

System.out.println (restoreIpAddresses

( "25525511135" ). toString ());

}
}

 
// This code is provided by Nidhi the Slim.

python3

# Python code to check for a valid possible IP

 
# The function checks if there are IP numbers
# valid or not.

def is_valid (ip):

 

# Divide by & quot ;. & quot;

ip = ip.split ( "." )

 

# Checking corner cases

for i in ip:

if len (i) & gt; 3 or int (i) & lt; 0 or int (i) & gt; 255 :

return False

if len (i) & gt; 1 and int (i) = = 0 :

return False

if len (i) & gt; 1 and int (i)! = 0 and i [ 0 ] = = `0` :

return False

  return True

  
# The function converts the string to an IP address

def convert (s):

sz = len (s)

 

# Check line size

if sz & gt; 12 :

return []

snew = s

l = []

-

# Generate different combinations.

for i in range ( 1 , sz - 2 ) :

for j in range (i + 1 , sz - 1 ):

for k in range (j + 1 , sz):

code class = "plain">] = = `0` :

return False

return True

  
# The function converts the string to an IP address

def convert (s):

sz = len (s)

 

# Check line size

if sz & gt; 12 :

return []

snew = s

l = []

-

# Generate different combinations.

for i in range (