Padrão 5: Codificação e design

Nem todo problema de string é sobre buscar um padrão — alguns são sobre representar dados. Como transformar uma lista de strings em uma única string e depois recuperá-la exatamente? A resposta ensina um princípio que vai bem além de strings.

Tentou? A primeira ideia quase sempre é juntar com um separador (vírgula, #) — e ela quebra assim que um dado contém esse separador (veja o caso "a#2#b"). A teoria abaixo mostra por que separadores são ambíguos e qual é a solução robusta.

A teoria: o problema da ambiguidade

Quero juntar ["abc", "de"] numa só string para transmitir, e depois separar de volta. A ideia ingênua: juntar com uma vírgula → "abc,de". Parece funcionar... até um dos dados conter o separador:

["a,b", "c"]  →  "a,b,c"  →  separando por ","  →  ["a", "b", "c"]  ✗

Recuperamos 3 strings em vez de 2. Qualquer separador escolhido pode aparecer nos dados — esse é o problema fundamental de delimitadores. Trocar a vírgula por outro caractere só empurra o problema: e se o dado contiver esse caractere também?

A solução: comprimento como prefixo (length-prefix)

Em vez de marcar onde cada pedaço termina (um separador, que pode colidir), marque quanto cada pedaço mede antes dele:

formato:  <comprimento>#<conteúdo><comprimento>#<conteúdo>...

["abc", "de"]  →  "3#abc2#de"

Para decodificar: leia o número até o #, e então pegue exatamente aquela quantidade de caracteres como o conteúdo — sem nunca interpretar o que vem dentro. O # nunca é ambíguo porque você só o procura na posição do comprimento; os caracteres do conteúdo são lidos por contagem, não por busca. Isso funciona mesmo que um dado contenha #, números, ou outra string codificada inteira.

Os sinais (o padrão de design)

• "Serializar / desserializar", "codificar / decodificar", "transmitir e reconstruir".
• O dado pode conter qualquer caractere (não há separador seguro).
• Reaparece forte na seção Árvores (serializar uma árvore binária é o mesmo princípio: registrar estrutura sem ambiguidade).

Exemplo — Encode and Decode Strings

"Escreva encode(lista) → string e decode(string) → lista que funcionem para qualquer conteúdo."

Repare no terceiro dado: "a#2#b" contém # e dígitos — exatamente o que quebraria um separador. Com length-prefix, ele volta intacto, porque o decodificador conta caracteres em vez de procurar separadores.

Por que é O(n)?

• encode: percorre cada string uma vez para montar a saída — O(n) no total de caracteres.
• decode: o ponteiro i avança pelo string codificado sem nunca voltar (lê o número, pula o conteúdo) — O(n). Cada caractere é visitado uma vez.
• Espaço O(n) para a saída, que é inevitável (é o resultado).

Por que esta aula importa além de strings

Este é o seu primeiro problema de design: a pergunta não é "qual o truque esperto?", mas "qual representação evita ambiguidade?". O princípio length-prefix — guardar o tamanho para não depender de delimitadores — é usado em protocolos de rede de verdade e volta na serialização de árvores (seção Árvores). Reconhecer "isto é um problema de representação" já é meio caminho.

Resumo

• Codificação é um problema de design/representação, não de truque.
• Separadores são ambíguos (o dado pode contê-los); length-prefix resolve: conte os caracteres em vez de procurar delimitadores.
• encode/decode em O(n); o ponteiro de decode nunca volta.
• O princípio reaparece na serialização de árvores.

Última parada: a síntese da seção String e o quiz antes da prova final.