Playground: Restore IP Addresses

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

Clase anteriorSiguiente clase

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")