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 el formato 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:
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.
Primero, colocaremos 3 puntos en la string dada y luego probaremos todas las combinaciones posibles para los 3 puntos.
Caso de esquina para validez:
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.
Enfoque: divida la string con ‘ . ‘ y luego verifique todos los casos de esquina. Antes de ingresar al bucle, verifique el tamaño de la string. Genere todas las combinaciones posibles utilizando bucles a través de la string. Si se encuentra que la IP es válida, devuelva la dirección IP; de lo contrario, simplemente devuelva la lista vacía.
A continuación se muestra la implementación del enfoque anterior:
Implementación:
C++
// C++ program to generate all possible
// valid IP addresses from given string
#include <bits/stdc++.h>
using namespace std;
// Function checks whether IP digits
// are valid or not.
int is_valid(string ip)
{
// Splitting by "."
vector<string> ips;
string ex = "";
for (int i = 0; i < ip.size(); i++) {
if (ip[i] == '.') {
ips.push_back(ex);
ex = "";
}
else {
ex = ex + ip[i];
}
}
ips.push_back(ex);
// Checking for the corner cases
// cout << ip << endl;
for (int i = 0; i < ips.size(); i++) {
// cout << ips[i] <<endl;
if (ips[i].length() > 3
|| stoi(ips[i]) < 0
|| stoi(ips[i]) > 255)
return 0;
if (ips[i].length() > 1
&& stoi(ips[i]) == 0)
return 0;
if (ips[i].length() > 1
&& stoi(ips[i]) != 0
&& ips[i][0] == '0')
return 0;
}
return 1;
}
// Function converts string to IP address
void convert(string ip)
{
int l = ip.length();
// Check for string size
if (l > 12 || l < 4) {
cout << "Not Valid IP Address";
}
string check = ip;
vector<string> ans;
// Generating different combinations.
for (int i = 1; i < l - 2; i++) {
for (int j = i + 1; j < l - 1; j++) {
for (int k = j + 1; k < l; k++) {
check = check.substr(0, k) + "."
+ check.substr(k);
check
= check.substr(0, j) + "."
+ check.substr(j);
check
= check.substr(0, i) + "."
+ check.substr(i);
// cout<< check <<endl;
// Check for the validity of combination
if (is_valid(check)) {
ans.push_back(check);
std::cout << check << '\n';
}
check = ip;
}
}
}
}
// Driver code
int main()
{
string A = "25525511135";
string B = "25505011535";
convert(A);
convert(B);
return 0;
}
// This code is contributed by Harshit
Java
// Java Program to generate all possible
// valid IP addresses from given string
import java.util.*;
class GFG {
// Function to restore Ip Addresses
public static ArrayList<String>
restoreIpAddresses(String A)
{
if (A.length() < 3 || A.length() > 12)
return new ArrayList<>();
return convert(A);
}
private static ArrayList<String>
convert(String s)
{
ArrayList<String> l = new ArrayList<>();
int size = s.length();
String snew = s;
for (int i = 1; i < size - 2;
i++) {
for (int j = i + 1;
j < size - 1; j++) {
for (int k = j + 1;
k < 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<String>() {
public int compare(String o1, String o2)
{
String a1[] = o1.split("[.]");
String a2[] = o2.split("[.]");
int result = -1;
for (int i = 0; i < 4
&& 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() > 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;
}
// Driver Code
public static void main(String[] args)
{
System.out.println(
restoreIpAddresses(
"25525511135")
.toString());
}
}
// This code is contributed by Nidhi Hooda.
Python3
# Python3 code to check valid possible IP
# Function checks whether IP digits
# are valid or not.
def is_valid(ip):
# Splitting by "."
ip = ip.split(".")
# Checking for the corner cases
for i in ip:
if (len(i) > 3 or int(i) < 0 or
int(i) > 255):
return False
if len(i) > 1 and int(i) == 0:
return False
if (len(i) > 1 and int(i) != 0 and
i[0] == '0'):
return False
return True
# Function converts string to IP address
def convert(s):
sz = len(s)
# Check for string size
if sz > 12:
return []
snew = s
l = []
# Generating different combinations.
for i in range(1, sz - 2):
for j in range(i + 1, sz - 1):
for k in range(j + 1, sz):
snew = snew[:k] + "." + snew[k:]
snew = snew[:j] + "." + snew[j:]
snew = snew[:i] + "." + snew[i:]
# Check for the validity of combination
if is_valid(snew):
l.append(snew)
snew = s
return l
# Driver code
A = "25525511135"
B = "25505011535"
print(convert(A))
print(convert(B))
Javascript
<script>
// JavaScript program to generate all possible
// valid IP addresses from given string
// Function checks whether IP digits
// are valid or not.
function is_valid(ip)
{
// Splitting by "."
let ips = new Array();
let ex = "";
for (let i = 0; i < ip.length; i++) {
if (ip[i] == '.') {
ips.push(ex);
ex = "";
}
else {
ex = ex + ip[i];
}
}
ips.push(ex);
// Checking for the corner cases
for(let i = 0; i < ips.length; i++) {
if (ips[i].length > 3
|| parseInt(ips[i]) < 0
|| parseInt(ips[i]) > 255)
return 0;
if (ips[i].length > 1
&& parseInt(ips[i]) == 0)
return 0;
if (ips[i].length > 1
&& parseInt(ips[i]) != 0
&& ips[i][0] == '0')
return 0;
}
return 1;
}
// Function converts string to IP address
function convert(ip)
{
let l = ip.length;
// Check for string size
if (l > 12 || l < 4) {
document.write("Not Valid IP Address");
}
let check = ip;
let ans = new Array();
// Generating different combinations.
for (let i = 1; i < l - 2; i++) {
for (let j = i + 1; j < l - 1; j++) {
for (let k = j + 1; k < l; k++) {
check = check.substring(0, k) + "."
+ check.substring(k,check.length);
check
= check.substring(0, j) + "."
+ check.substring(j,check.length);
check
= check.substring(0, i) + "."
+ check.substring(i,check.length);
// Check for the validity of combination
if (is_valid(check)) {
ans.push(check);
document.write(check,"</br>");
}
check = ip;
}
}
}
}
// Driver code
let A = "25525511135";
let B = "25505011535";
convert(A);
convert(B);
// This code is contributed by shinjanpatra
</script>
Producción
255.255.11.135 255.255.111.35
Análisis de Complejidad:
- Complejidad de tiempo: O(n^3) , donde n es la longitud de la string
Se necesitan tres recorridos anidados de la string, donde n siempre es menor que 12. - Espacio Auxiliar: O(n).
Como se necesita espacio adicional.
Otro enfoque eficiente (programación dinámica): existe un enfoque dp para este problema y se puede resolver en complejidad de tiempo O(n*4*3)=O(12n)=O(n) y complejidad de espacio O(4n).
Enfoque: Sabemos que solo hay 4 partes de la IP. Comenzamos a iterar desde el final de la string y vamos al comienzo de la string. Creamos una array dp 2D de tamaño (4 x N). Solo puede haber 2 valores en la array dp, es decir, 1 (verdadero) o 0 (falso). dp[0][i] dice si podemos crear 1 parte de IP desde la substring que comienza desde i hasta el final de la string. De manera similar, dp[1][i] indica si podemos crear 2 partes de IP a partir de la substring que comienza desde i hasta el final de la string.
Después de crear la array dp, comenzamos a crear las direcciones IP válidas. Comenzamos desde la esquina inferior izquierda de la array 2D dp. Solo iteramos 12 veces (en el peor de los casos), pero esas también serán las direcciones IP válidas porque solo formamos direcciones IP válidas.
Implementación:
Java
// Java Program to generate all possible
// valid IP addresses from given string
import java.util.*;
class GFG
{
public static ArrayList<String> list;
// Function to restore Ip Addresses
public static ArrayList<String>
restoreIpAddresses(String s)
{
int n = s.length();
list = new ArrayList<>();
if (n < 4 || n > 12)
return list;
// initialize the dp array
int dp[][] = new int[4][n];
for (int i = 0; i < 4; i++)
{
for (int j = n - 1; j >= 0; j--)
{
if (i == 0)
{
// take the substring
String sub = s.substring(j);
if (isValid(sub))
{
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 temp
= s.substring(j, j + k);
if (isValid(temp))
{
if (j + k < n
&& dp[i - 1][j + k]
== 1)
{
dp[i][j] = 1;
break;
}
}
}
}
}
}
}
if (dp[3][0] == 0)
return list;
// Call function createIpfromDp
createIpFromDp(dp, 3, 0, s, "");
return list;
}
public static void createIpFromDp(int dp[][],
int r,
int c, String s,
String ans)
{
if (r == 0)
{
ans += s.substring(c);
list.add(ans);
return;
}
for (int i = 1;
i <= 3 && c + i < s.length();
i++)
{
if (isValid(s.substring(c, c + i))
&& dp[r - 1] == 1)
{
createIpFromDp(dp, r - 1, c + i, s,
ans +
s.substring(c, c + i)
+ ".");
}
}
}
private static boolean isValid(String ip)
{
String a[] = ip.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;
}
// Driver Code
public static void main(String[] args)
{
// Function call
System.out.println(
restoreIpAddresses("25525511135").toString());
}
}
// This code is contributed by Nidhi Hooda.
C#
// Include namespace system
using System;
using System.Collections.Generic;
public class GFG {
static List<String> list;
// Function to restore Ip Addresses
public static List<String> restoreIpAddresses(String s)
{
var n = s.Length;
list = new List<String>();
if (n < 4 || n > 12) {
return list;
}
// initialize the dp array
int[, ] dp = new int[4, n];
for (int i = 0; i < 4; i++) {
for (int j = n - 1; j >= 0; j--) {
if (i == 0)
{
// take the substring
var sub = s.Substring(j);
if (GFG.isValid(sub)) {
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++) {
var temp
= s.Substring(j, j + k - j);
if (GFG.isValid(temp)) {
if (j + k < n
&& dp[i - 1, j + k]
== 1) {
dp[i, j] = 1;
break;
}
}
}
}
}
}
}
if (dp[3, 0] == 0) {
return list;
}
// Call function createIpfromDp
GFG.createIpFromDp(dp, 3, 0, s, "");
return list;
}
public static void createIpFromDp(int[, ] dp, int r,
int c, String s,
String ans)
{
if (r == 0) {
ans += s.Substring(c);
list.Add(ans);
return;
}
for (int i = 1; i <= 3 && c + i < s.Length; i++) {
if (GFG.isValid(s.Substring(c, c + i - c))
&& dp[r - 1, c + i] == 1) {
GFG.createIpFromDp(
dp, r - 1, c + i, s,
ans + s.Substring(c, c + i - c) + ".");
}
}
}
private static bool isValid(String ip)
{
String[] a = ip.Split("[.]");
foreach(String s in a)
{
var i = int.Parse(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[0] == '0') {
return false;
}
}
return true;
}
// Driver Code
public static void Main(String[] args)
{
// Function call
Console.WriteLine(string.Join(
",", (GFG.restoreIpAddresses("25525511135"))
.ToArray()));
}
}
// This code is contributed by Aarti_Rathi
Producción
[255.255.11.135, 255.255.111.35]
Análisis de Complejidad:
- Complejidad de tiempo: O(n), donde n es la longitud de la string. La creación de la array dp tomaría O(4*n*3) = O(12n) = O(n). La creación de IP válida desde la array dp tomaría O (n).
- Espacio Auxiliar: O(n) . Como array dp tiene espacio extra de tamaño (4 xn). Significa O(4n).
Otro enfoque: (usando la recursividad)
Implementación:
C++
#include <iostream>
#include <vector>
using namespace std;
void solve(string s, int i, int j, int level, string temp,
vector<string>& res)
{
if (i == (j + 1) && level == 5) {
res.push_back(temp.substr(1));
}
// Digits of a number ranging 0-255 can lie only between
// 0-3
for (int k = i; k < i + 3 && k <= j; k++) {
string ad = s.substr(i, k - i + 1);
// Return if string starting with '0' or it is
// greater than 255.
if ((s[i] == '0'&&ad.size()>1) || stol(ad) > 255)
return;
// Recursively call for another level.
solve(s, k + 1, j, level + 1, temp + '.' + ad, res);
}
}
int main()
{
string s = "25525511135";
int n = s.length();
vector<string> ans;
solve(s, 0, n - 1, 1, "", ans);
for (string s : ans)
cout << s << endl;
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
static void solve(String s, int i, int j, int level, String temp,
ArrayList<String>res)
{
if (i == (j + 1) && level == 5) {
res.add(temp.substring(1));
}
// Digits of a number ranging 0-255 can lie only between
// 0-3
for (int k = i; k < i + 3 && k <= j; k++) {
String ad = s.substring(i, k + 1);
// Return if string starting with '0' or it is
// greater than 255.
if ((s.charAt(i) == '0'&& ad.length()>1 ) || Integer.valueOf(ad) > 255)
return;
// Recursively call for another level.
solve(s, k + 1, j, level + 1, temp + '.' + ad, res);
}
}
/* Driver program to test above function*/
public static void main(String args[])
{
String s = "25525511135";
int n = s.length();
ArrayList<String> ans = new ArrayList<>();
solve(s, 0, n - 1, 1, "", ans);
for (String s1 : ans)
System.out.println(s1);
}
}
// This code is contributed by shinjanpatra.
Python3
# Python code for the above approach def solve(s, i, j, level, temp, res): if (i == (j + 1) and level == 5): res.append(temp[1:]) # Digits of a number ranging 0-255 can lie only between # 0-3 k = i while(k < i + 3 and k <= j): ad = s[i: k + 1] # Return if string starting with '0' or it is # greater than 255. if ((s[i] == '0' and len(ad) > 1) or int(ad) > 255): return # Recursively call for another level. solve(s, k + 1, j, level + 1, temp + '.' + ad, res) k += 1 # driver code s = "25525511135" n = len(s) ans = [] solve(s, 0, n - 1, 1, "", ans) for s in ans: print(s) # This code is contributed by shinjanpatra
Javascript
<script>
// Simple JavaScript program
function solve(s,i,j,level, temp,res)
{
if (i == (j + 1) && level == 5) {
res.push(temp.substring(1,));
}
// Digits of a number ranging 0-255 can lie only between
// 0-3
for (let k = i; k < i + 3 && k <= j; k++) {
let ad = s.substring(i, k + 1);
// Return if string starting with '0' or it is
// greater than 255.
if ((s[i] == '0' && ad.length > 1) || parseInt(ad) > 255)
return;
// Recursively call for another level.
solve(s, k + 1, j, level + 1, temp + '.' + ad, res);
}
}
// driver code
let s = "25525511135";
let n = s.length;
let ans = [];
solve(s, 0, n - 1, 1, "", ans);
for (let s of ans)
document.write(s,"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
255.255.11.135 255.255.111.35
Publicación traducida automáticamente
Artículo escrito por Abhishek Sharma 44 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA