Empaquetar palabras en un solo string
La misión
Problema
Escribe pack(words), que convierte una lista de strings (cadenas) en un solo string, y unpack(text), que convierte ese string de vuelta en la lista original. Cada palabra se escribe como su longitud en decimal, luego un # y luego la palabra misma. Las palabras pueden estar vacías y contener cualquier carácter, incluidos dígitos y #, así que unpack nunca debe buscar un separador dentro de una palabra.
Ejemplos
Input: words = ["hi", "#1"]
Output: pack -> "2#hi2##1"
unpack -> ["hi", "#1"]
Por qué: tras leer "2#", los dos caracteres siguientes se toman enteros, sean "#" o no
Input: words = ["", "a"]
Output: pack -> "0#1#a"
Por qué: una palabra vacía también lleva su longitud, así que sobrevive al viaje de ida y vuelta
Input: words = []
Output: pack -> ""
unpack -> []
Por qué: caso límite: nada que escribir y nada que leer
Pistas
0 / 3
Unir con un separador falla en cuanto una palabra contiene ese separador. La longitud delante de cada palabra es lo que elimina la ambigüedad.
El primer # después de una longitud siempre marca el final de esa longitud, porque una longitud solo tiene dígitos. Todo lo que viene después se cuenta, no se busca.
Lleva una posición de lectura. Lee dígitos hasta el siguiente #, conviértelos en un número n, toma exactamente los n caracteres que siguen al # y mueve la posición de lectura más allá de ellos. Repite hasta que la posición llegue al final.
- Tiempo objetivo
- O(L)
- Espacio objetivo
- O(L)
Restricciones
- words may be empty
- words may contain any character, including # and digits
Solución
El prefijo de longitud le dice al lector exactamente cuántos caracteres tomar, así que el contenido de una palabra nunca importa. Leer una longitud es seguro porque una longitud solo tiene dígitos, lo que convierte al primer # que le sigue en el verdadero final del número. Cada carácter se visita un número constante de veces al empaquetar y al desempaquetar. El tiempo es O(L) para L caracteres en total, y el espacio es O(L) para la salida.
def pack(words):
return "".join(f"{len(w)}#{w}" for w in words)
def unpack(text):
words, i = [], 0
while i < len(text):
hash_at = text.index("#", i) # end of the length digits
n = int(text[i:hash_at])
words.append(text[hash_at + 1:hash_at + 1 + n])
i = hash_at + 1 + n # jump over the word, never into it
return words
print(pack(["hi", "#1"])) # -> 2#hi2##1
print(unpack("2#hi2##1")) # -> ['hi', '#1']
print(unpack(pack(["", "a"]))) # -> ['', 'a']
print(unpack(pack([]))) # -> []¿Lo que te frena es la idea y no el código? Encode and Decode Strings lo explica.