Pular para o conteúdo

Operações de uma trie

Fácil#trie#design~20 min

A missão

Problema

Construa uma trie (árvore de prefixos) para palavras em minúsculas com três operações. insert(word) armazena uma palavra. has_word(word) informa se exatamente essa palavra foi armazenada. has_prefix(prefix) informa se alguma palavra armazenada começa com o prefixo não vazio dado. Cada operação deve custar tempo proporcional ao comprimento do seu argumento, não importa quantas palavras estejam armazenadas.

Exemplos

Input:  insert("apple"), has_word("apple"), has_word("app"), has_prefix("app")
Output: True, False, True
Por quê: "app" inicia uma palavra armazenada, mas nunca foi armazenada por si só
Input:  insert("apple"), insert("app"), has_word("app")
Output: True
Input:  (nothing inserted), has_word("app"), has_prefix("a")
Output: False, False
Por quê: edge case: uma árvore vazia não contém palavras nem prefixos

Dicas

0 / 3

Tempo-alvo
O(L)
Espaço-alvo
O(total characters)

Restrições

  • words are lowercase
  • prefixes are non-empty

Travou na ideia, e não no código? O básico de tries explica isso.

Python 3Ctrl+Enter executa