Empacotar palavras em uma string
A missão
Problema
Escreva pack(words), que transforma uma lista de strings em uma única string, e unpack(text), que transforma essa string de volta na lista original. Cada palavra é escrita como o seu tamanho em decimal, seguido de um # e da própria palavra. As palavras podem ser vazias e conter qualquer caractere, inclusive dígitos e #, então unpack nunca pode procurar um separador dentro de uma palavra.
Exemplos
Input: words = ["hi", "#1"]
Output: pack -> "2#hi2##1"
unpack -> ["hi", "#1"]
Por quê: depois de ler "2#", os dois caracteres seguintes são pegos inteiros, sejam "#" ou não
Input: words = ["", "a"]
Output: pack -> "0#1#a"
Por quê: uma palavra vazia ainda recebe o seu tamanho, então ela sobrevive à ida e volta
Input: words = []
Output: pack -> ""
unpack -> []
Por quê: edge case: nada para escrever e nada para ler
Dicas
0 / 3
Juntar com um separador quebra assim que uma palavra contém esse separador. O tamanho na frente de cada palavra é o que elimina a ambiguidade.
O primeiro # depois de um tamanho é sempre o fim desse tamanho, porque um tamanho é feito só de dígitos. Tudo o que vem depois dele é contado, não procurado.
Mantenha uma posição de leitura. Leia os dígitos até o próximo #, transforme-os em um número n, pegue exatamente os n caracteres depois do # e mova a posição de leitura para depois deles. Repita até a posição chegar ao fim.
- Tempo-alvo
- O(L)
- Espaço-alvo
- O(L)
Restrições
- words may be empty
- words may contain any character, including # and digits
Solução
O prefixo de tamanho diz ao leitor exatamente quantos caracteres pegar, então o conteúdo de uma palavra nunca importa. Ler um tamanho é seguro porque um tamanho é feito só de dígitos, o que torna o primeiro # depois dele o verdadeiro fim do número. Cada caractere é visitado um número constante de vezes ao empacotar e ao desempacotar. O tempo é O(L) para L caracteres no total, e o espaço é O(L) para a saída.
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([]))) # -> []Travou na ideia, e não no código? Codificar e decodificar strings explica isso.