Operações de uma trie
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
Verificar um prefixo contra cada palavra armazenada custa tempo para cada palavra. Palavras que começam do mesmo jeito deveriam dividir o trabalho de armazenar esse começo.
Armazene as palavras como caminhos de filhos aninhados, um caractere por passo, para que palavras com um prefixo comum compartilhem os mesmos primeiros nós. Um caminho existir não é o mesmo que uma palavra terminar ali, então o fim de uma palavra precisa do seu próprio marcador.
Para inserir, percorra a partir da raiz criando cada filho que faltar e depois coloque um marcador de fim no último nó. Nas duas consultas, percorra do mesmo jeito e informe falha assim que um caractere não tiver filho. Uma consulta de prefixo tem sucesso se o percurso chegar ao fim; uma consulta de palavra também precisa do marcador de fim no nó final.
- Tempo-alvo
- O(L)
- Espaço-alvo
- O(total characters)
Restrições
- words are lowercase
- prefixes are non-empty
Solução
Cada nó é um dicionário de caractere para nó filho, então uma palavra é um caminho a partir da raiz, e prefixos compartilhados compartilham nós. Uma chave sentinela marca os nós em que uma palavra armazenada realmente termina, e é isso que separa um “app” armazenado de um mero prefixo de “apple”. As duas consultas usam o mesmo percurso e só diferem em exigir ou não a sentinela no fim. Toda operação toca um nó por caractere, então cada uma custa O(L) para um argumento de comprimento L, e a árvore usa espaço O(total de caracteres armazenados).
class PrefixTree:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {}) # shared prefixes share nodes
node["$"] = True # a whole word ends here
def _walk(self, s): # the node s leads to, or None
node = self.root
for ch in s:
if ch not in node:
return None
node = node[ch]
return node
def has_word(self, word):
node = self._walk(word)
return node is not None and "$" in node
def has_prefix(self, prefix):
return self._walk(prefix) is not None
t = PrefixTree(); t.insert("apple")
print(t.has_word("apple"), t.has_word("app"), t.has_prefix("app")) # -> True False True
t.insert("app"); e = PrefixTree()
print(t.has_word("app"), e.has_word("app"), e.has_prefix("a")) # -> True False FalseTravou na ideia, e não no código? O básico de tries explica isso.