Playground: Restore IP Addresses

Clase 43 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Comentarios

Carlos Hernandez

student•

El Ejemplo 3 está mal

Sí hay combinaciones válidas, por ejemplo:

0.19.216.81 0.192.168.1 0.192.16.81

John Eduard Meneses González

student•

My Solution!!

José Ramón García

student•

Comparto mi solución en Python

def ip_addresses(numbers):
    size = {0:12, 1:9, 2:6, 3:3, 4:0}
    ip = []
    valid_ips = []

    def dfs(level=0, numbers=None):
        if len(numbers) > size[level] or (level==0 and len(numbers) < 4):
            return
        if level == 4:
            valid_ips.append(''.join(ip[:-1]))

        for i in range(1, min(4, len(numbers) + 1)):
            part = numbers[0:i]
            if  int(part) <= 255 and (len(part) == 1 or part[0] != '0'): # If is not len = 1, then len 2 or 3, so the fist digit can be 0
                ip.append(part)
                ip.append('.')
                dfs(level + 1, numbers=numbers[i:])
                ip.pop()
                ip.pop()
        
    dfs(level=0, numbers=numbers)
    return valid_ips

Carlos Hernandez

student•

Mi solución:

const isValidIp = (ip) => {
    const ipComponents = ip.split('.');

    if (ipComponents.length !== 4) return false;

    let isValid = true;

    for (let index = 0; index < ipComponents.length; index++) {
        const ipComponent = ipComponents[index];

        if (parseInt(ipComponent) > 255 || (ipComponent.length > 1 && ipComponent[0] === '0')) {
            isValid = false;
            break;
        }
    }

    return isValid;
}

const appendPossibleCombination = (i, currentIp, ipString, combinations) => {
    if (i >= ipString.length) {
        if (isValidIp(currentIp)) {
            combinations.push(currentIp);
        }
        return;
    }

    if (currentIp) {
        currentIp = currentIp + '.';
    } 

    appendPossibleCombination(i + 1, `${currentIp}${ipString[i] || ''}`, ipString, combinations);
    appendPossibleCombination(i + 2, `${currentIp}${ipString[i] || ''}${ipString[i+1] || ''}`, ipString, combinations);
    appendPossibleCombination(i + 3, `${currentIp}${ipString[i] || ''}${ipString[i+1] || ''}${ipString[i+2] || ''}`, ipString, combinations);
}

const restoreIpAddresses = (ipString) => {
    let combinations = [];

    appendPossibleCombination(0, '', ipString, combinations);

    return Array.from(new Set(combinations));
}

Miguel Angel Reyes Moreno

student•

Comparto mi código en Python con algunos ejemplos:


from typing import List





class Solution:

&#x20;   def restoreIpAddresses(self, s: str) -> List\[str]:

&#x20;       if len(s) < 4 or len(s) > 12:

&#x20;           return \[]





&#x20;       result = \[]



&#x20;       def backtrack(start: int, path: List\[str]):

&#x20;           if len(path) == 4 and start == len(s):

&#x20;               result.append(".".join(path))

&#x20;               return



&#x20;           if len(path) == 4:

&#x20;               return



&#x20;           for length in range(1,4):

&#x20;               if start + length <= len(s):

&#x20;                   segment = s\[start:start + length]

&#x20;                   if (len(segment) > 1 and segment\[0] == "0" or int(segment) > 255):

&#x20;                       continue

&#x20;                   backtrack(start + length, path + \[segment])





&#x20;       backtrack(0, \[])

&#x20;       return result





solution = Solution()

solution.restoreIpAddresses("25525511135")

solution.restoreIpAddresses("0000")

solution.restoreIpAddresses("101023")

def ip_addresses(numbers):
    size = {0:12, 1:9, 2:6, 3:3, 4:0}
    ip = []
    valid_ips = []

    def dfs(level=0, numbers=None):
        if len(numbers) > size[level] or (level==0 and len(numbers) < 4):
            return
        if level == 4:
            valid_ips.append(''.join(ip[:-1]))

        for i in range(1, min(4, len(numbers) + 1)):
            part = numbers[0:i]
            if  int(part) <= 255 and (len(part) == 1 or part[0] != '0'): # If is not len = 1, then len 2 or 3, so the fist digit can be 0
                ip.append(part)
                ip.append('.')
                dfs(level + 1, numbers=numbers[i:])
                ip.pop()
                ip.pop()
        
    dfs(level=0, numbers=numbers)
    return valid_ips

const isValidIp = (ip) => {
    const ipComponents = ip.split('.');

    if (ipComponents.length !== 4) return false;

    let isValid = true;

    for (let index = 0; index < ipComponents.length; index++) {
        const ipComponent = ipComponents[index];

        if (parseInt(ipComponent) > 255 || (ipComponent.length > 1 && ipComponent[0] === '0')) {
            isValid = false;
            break;
        }
    }

    return isValid;
}

const appendPossibleCombination = (i, currentIp, ipString, combinations) => {
    if (i >= ipString.length) {
        if (isValidIp(currentIp)) {
            combinations.push(currentIp);
        }
        return;
    }

    if (currentIp) {
        currentIp = currentIp + '.';
    } 

    appendPossibleCombination(i + 1, `${currentIp}${ipString[i] || ''}`, ipString, combinations);
    appendPossibleCombination(i + 2, `${currentIp}${ipString[i] || ''}${ipString[i+1] || ''}`, ipString, combinations);
    appendPossibleCombination(i + 3, `${currentIp}${ipString[i] || ''}${ipString[i+1] || ''}${ipString[i+2] || ''}`, ipString, combinations);
}

const restoreIpAddresses = (ipString) => {
    let combinations = [];

    appendPossibleCombination(0, '', ipString, combinations);

    return Array.from(new Set(combinations));
}

from typing import List

class Solution:

&#x20;   def restoreIpAddresses(self, s: str) -> List\[str]:

&#x20;       if len(s) < 4 or len(s) > 12:

&#x20;           return \[]

&#x20;       result = \[]

&#x20;       def backtrack(start: int, path: List\[str]):

&#x20;           if len(path) == 4 and start == len(s):

&#x20;               result.append(".".join(path))

&#x20;               return

&#x20;           if len(path) == 4:

&#x20;               return

&#x20;           for length in range(1,4):

&#x20;               if start + length <= len(s):

&#x20;                   segment = s\[start:start + length]

&#x20;                   if (len(segment) > 1 and segment\[0] == "0" or int(segment) > 255):

&#x20;                       continue

&#x20;                   backtrack(start + length, path + \[segment])

&#x20;       backtrack(0, \[])

&#x20;       return result

solution = Solution()

solution.restoreIpAddresses("25525511135")

solution.restoreIpAddresses("0000")

solution.restoreIpAddresses("101023")

Playground: Restore IP Addresses

Introducción

Grafos y Árboles: Estructuras de Datos Avanzadas

Estructuras de Datos: Introducción a Árboles y Sus Propiedades

Recursión: Concepto y Aplicaciones Prácticas con Ejemplos

Aplicaciones Prácticas de Grafos en Tecnología e Industria

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Búsqueda en Profundidad (DFS) en Árboles y Grafos

Implementación de DFS recursivo para búsqueda en árboles

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Recorridos y Profundidad en Árboles Binarios y Enearios

Suma de Caminos en Árboles Binarios

Suma de Números de Raíz a Hoja en Árboles

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Resolución del Problema de Número de Islas con DFS

Conteo de Islas en Matrices con DFS

Playground: Number of Islands

Implementación de "Número de Islas" con Recursión en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles

Implementación de BFS en Árboles usando Python

Movimiento mínimo de caballo en ajedrez infinito

Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez

Playground: Minimum Knights Moves

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

Propagación de Plagas en Cultivos: Cálculo de Días para Contagio Total

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Propagación de Plagas en Matrices usando BFS en Java

Construcción de Puentes Cortos entre Islas en Matrices Binarias

Resolución del Problema Shortest Bridge con DFS y BFS

Playground: Shortest Bridge Between Islands

Búsqueda del camino más corto entre islas usando BFS en Python

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

Algoritmo Backtracking: Solución de Problemas Complejos

Combinaciones de Letras en Números Telefónicos

Combinaciones de Letras a partir de un Número de Teléfono

Generación de combinaciones de letras con teclados numéricos en C++

Playground: Letter Combinations of a Phone Number

Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

Generación de IPs válidas con backtracking en C++

Playground: Restore IP Addresses

Búsqueda de Palabras en Matrices: Solución y Complejidad

Búsqueda de Palabras en Matrices usando Backtracking y DFS

Playgrund: Word Search

Implementación de búsqueda de palabras en matrices con DFS en JavaScript

Resolución del problema de las n reinas en ajedrez

Ejercicios de Backtracking: Combinaciones y Permutaciones

Combinaciones y Permutaciones con Backtracking

Próximos pasos

Algoritmos de Grafos: MIN/MAX-HIP, TRI, Topological Sort y Dijkstra

Algoritmos y Estructuras de Datos en la Ingeniería