Programa para generar todas las posibles direcciones IP válidas a partir de una string dada | conjunto 2

Dada una string que contiene solo dígitos, restáurela devolviendo todas las posibles combinaciones válidas de direcciones IP. 
Una dirección IP válida debe tener la forma de ABCD , donde A , B , C y D son números del 0 al 255 . Los números no pueden tener el prefijo 0 a menos que sean 0 .
Ejemplos: 
 

Entrada: str = “25525511135” 
Salida: 
255.255.11.135 
255.255.111.35
Entrada: str = “11111011111” 
Salida: 
111.110.11.111 
111.110.111.11 
 

Enfoque: Este problema se puede resolver usando backtracking . En cada llamada tenemos tres opciones para crear un solo bloque de números de una dirección IP válida: 
 

1. Seleccione solo un dígito, agregue un punto y pase a seleccionar otros bloques (llamadas de función adicionales).
2. O seleccione dos dígitos al mismo tiempo, agregue un punto y avance más.
3. O seleccione tres dígitos consecutivos y pase al siguiente bloque.

Al final del cuarto bloque, si se han utilizado todos los dígitos y la dirección generada es una dirección IP válida, agréguela a los resultados y luego retroceda eliminando los dígitos seleccionados en la llamada anterior.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <iostream>
#include <vector>
using namespace std;
 
// Function to get all the valid ip-addresses
void GetAllValidIpAddress(vector<string>& result,
                          string givenString, int index,
                          int count, string ipAddress)
{
 
    // If index greater than givenString size
    // and we have four block
    if (givenString.size() == index && count == 4) {
 
        // Remove the last dot
        ipAddress.pop_back();
 
        // Add ip-address to the results
        result.push_back(ipAddress);
        return;
    }
 
    // To add one index to ip-address
    if (givenString.size() < index + 1)
        return;
 
    // Select one digit and call the
    // same function for other blocks
    ipAddress = ipAddress
                + givenString.substr(index, 1) + '.';
    GetAllValidIpAddress(result, givenString, index + 1,
                         count + 1, ipAddress);
 
    // Backtrack to generate another possible ip address
    // So we remove two index (one for the digit
    // and other for the dot) from the end
    ipAddress.erase(ipAddress.end() - 2, ipAddress.end());
 
    // Select two consecutive digits and call
    // the same function for other blocks
    if (givenString.size() < index + 2
        || givenString[index] == '0')
        return;
    ipAddress = ipAddress + givenString.substr(index, 2) + '.';
    GetAllValidIpAddress(result, givenString, index + 2,
                         count + 1, ipAddress);
 
    // Backtrack to generate another possible ip address
    // So we remove three index from the end
    ipAddress.erase(ipAddress.end() - 3, ipAddress.end());
 
    // Select three consecutive digits and call
    // the same function for other blocks
    if (givenString.size() < index + 3
        || stoi(givenString.substr(index, 3)) > 255)
        return;
    ipAddress += givenString.substr(index, 3) + '.';
    GetAllValidIpAddress(result, givenString, index + 3,
                         count + 1, ipAddress);
 
    // Backtrack to generate another possible ip address
    // So we remove four index from the end
    ipAddress.erase(ipAddress.end() - 4, ipAddress.end());
}
 
// Driver code
int main()
{
    string givenString = "25525511135";
 
    // Fill result vector with all valid ip-addresses
    vector<string> result;
    GetAllValidIpAddress(result, givenString, 0, 0, "");
 
    // Print all the generated ip-addresses
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << "\n";
    }
}

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
 
class GFG
{
   
  // Function to get all the valid ip-addresses
  static void GetAllValidIpAddress(ArrayList<String>result,
                                   String givenString,int index,
                                   int count, String ipAddress){
 
    // If index greater than givenString size
    // and we have four block
    if (givenString.length() == index && count == 4){
 
      // Remove the last dot
      ipAddress =  ipAddress.substring(0,ipAddress.length()-1);
 
      // Add ip-address to the results
      result.add(ipAddress);
      return;
    }
 
    // To add one index to ip-address
    if (givenString.length() < index + 1)
      return;
 
    // Select one digit and call the
    // same function for other blocks
    ipAddress = (ipAddress + givenString.substring(index , index + 1) + '.');
 
    GetAllValidIpAddress(result, givenString, index + 1, count + 1, ipAddress);
 
    // Backtrack to generate another possible ip address
    // So we remove two index (one for the digit
    // and other for the dot) from the end
    ipAddress = ipAddress.substring(0,ipAddress.length() - 2);
 
    // Select two consecutive digits and call
    // the same function for other blocks
    if (givenString.length() < index + 2 ||
        givenString.charAt(index) == '0')
      return;
 
    ipAddress = ipAddress + givenString.substring(index,index + 2) + '.';
    GetAllValidIpAddress(result, givenString, index + 2,
                         count + 1, ipAddress);
 
    // Backtrack to generate another possible ip address
    // So we remove three index from the end
    ipAddress = ipAddress.substring(0,ipAddress.length() - 3);
 
    // Select three consecutive digits and call
    // the same function for other blocks
    if (givenString.length() < index + 3 ||
        Integer.valueOf(givenString.substring(index,index + 3)) > 255)
      return;
    ipAddress += givenString.substring(index,index + 3) + '.';
    GetAllValidIpAddress(result, givenString,
                         index + 3, count + 1, ipAddress);
 
    // Backtrack to generate another possible ip address
    // So we remove four index from the end
    ipAddress = ipAddress.substring(0,ipAddress.length()-4);
  }      
  public static void main (String[] args) {
    String givenString = "25525511135";
 
    // Fill result vector with all valid ip-addresses
    ArrayList<String>result = new ArrayList<String>() ;
    String ipAddress = "";
    GetAllValidIpAddress(result, givenString, 0, 0,ipAddress);
 
    // Print all the generated ip-addresses
    for(int i = 0; i < result.size(); i++)
      System.out.println(result.get(i));
  }
}
 
// This code is contributed by shinjanpatra.

# Python3 implementation of the approach
 
# Function to get all the valid ip-addresses
def GetAllValidIpAddress(result, givenString,
                         index, count, ipAddress) :
 
    # If index greater than givenString size
    # and we have four block
    if (len(givenString) == index and count == 4) :
 
        # Remove the last dot
        ipAddress.pop();
 
        # Add ip-address to the results
        result.append(ipAddress);
        return;
 
    # To add one index to ip-address
    if (len(givenString) < index + 1) :
        return;
 
    # Select one digit and call the
    # same function for other blocks
    ipAddress = (ipAddress +
                 givenString[index : index + 1] + ['.']);
     
    GetAllValidIpAddress(result, givenString, index + 1,
                                 count + 1, ipAddress);
 
    # Backtrack to generate another possible ip address
    # So we remove two index (one for the digit
    # and other for the dot) from the end
    ipAddress = ipAddress[:-2];
 
    # Select two consecutive digits and call
    # the same function for other blocks
    if (len(givenString) < index + 2 or
            givenString[index] == '0') :
        return;
         
    ipAddress = ipAddress + givenString[index:index + 2] + ['.'];
    GetAllValidIpAddress(result, givenString, index + 2,
                                  count + 1, ipAddress);
 
    # Backtrack to generate another possible ip address
    # So we remove three index from the end
    ipAddress = ipAddress[:-3];
 
    # Select three consecutive digits and call
    # the same function for other blocks
    if (len(givenString)< index + 3 or
        int("".join(givenString[index:index + 3])) > 255) :
        return;
    ipAddress += givenString[index:index + 3] + ['.'];
    GetAllValidIpAddress(result, givenString,
                         index + 3, count + 1, ipAddress);
 
    # Backtrack to generate another possible ip address
    # So we remove four index from the end
    ipAddress = ipAddress[:-4];
 
# Driver code
if __name__ == "__main__" :
    givenString = list("25525511135");
 
    # Fill result vector with all valid ip-addresses
    result = [] ;
    GetAllValidIpAddress(result, givenString, 0, 0, []);
 
    # Print all the generated ip-addresses
    for i in range(len(result)) :
        print("".join(result[i]));
         
# This code is contributed by Ankitrai01

<script>
 
// JavaScript implementation of the approach
 
// Function to get all the valid ip-addresses
function GetAllValidIpAddress(result, givenString, index, count, ipAddress){
 
    // If index greater than givenString size
    // and we have four block
    if (givenString.length == index && count == 4){
 
        // Remove the last dot
        ipAddress =  ipAddress.substring(0,ipAddress.length-1);
 
        // Add ip-address to the results
        result.push(ipAddress);
        return;
    }
 
    // To add one index to ip-address
    if (givenString.length < index + 1)
        return;
 
    // Select one digit and call the
    // same function for other blocks
    ipAddress = (ipAddress + givenString.substring(index , index + 1) + '.');
     
    GetAllValidIpAddress(result, givenString, index + 1, count + 1, ipAddress);
 
    // Backtrack to generate another possible ip address
    // So we remove two index (one for the digit
    // and other for the dot) from the end
    ipAddress = ipAddress.substring(0,ipAddress.length - 2);
 
    // Select two consecutive digits and call
    // the same function for other blocks
    if (givenString.length < index + 2 ||
            givenString[index] == '0')
        return;
         
    ipAddress = ipAddress + givenString.substring(index,index + 2) + '.';
    GetAllValidIpAddress(result, givenString, index + 2,
                                  count + 1, ipAddress);
 
    // Backtrack to generate another possible ip address
    // So we remove three index from the end
    ipAddress = ipAddress.substring(0,ipAddress.length - 3);
 
    // Select three consecutive digits and call
    // the same function for other blocks
    if (givenString.length < index + 3 ||
        parseInt(givenString.substring(index,index + 3)) > 255)
        return;
    ipAddress += givenString.substring(index,index + 3) + ['.'];
    GetAllValidIpAddress(result, givenString,
                         index + 3, count + 1, ipAddress);
 
    // Backtrack to generate another possible ip address
    // So we remove four index from the end
    ipAddress = ipAddress.substring(0,ipAddress.length-4);
}
 
// Driver code
 
let givenString = "25525511135";
 
// Fill result vector with all valid ip-addresses
let result = [] ;
GetAllValidIpAddress(result, givenString, 0, 0, []);
 
// Print all the generated ip-addresses
for(let i=0;i<result.length;i++)
    document.write(result[i],"</br>");
         
// This code is contributed by shinjanpatra
 
</script>

255.255.11.135
255.255.111.35

Complejidad de Tiempo: O(1), Dado que el número total de direcciones IP son constantes
Espacio Auxiliar: O(1)