Implement Trie (Prefix Tree)

MédioTrie

+10

Uma trie, ou árvore de prefixos, armazena palavras para que consultas sobre seus inícios sejam rápidas. Crie uma para palavras em letras minúsculas com três operações: insert w adiciona a palavra w, search w informa se a própria palavra w foi inserida, e startsWith p informa se alguma palavra inserida começa com p. Uma palavra é considerada prefixo de si mesma.

Você recebe as operações em ordem em ops, e words[i] é a palavra ou o prefixo correspondente a ops[i]. Execute-as em uma única trie que começa vazia e retorne uma string por operação: "null" para uma inserção e "true" ou "false" para uma busca ou operação startsWith.

Função

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: as operações, na ordem em que são executadas
wordsstring-array: a palavra ou o prefixo de cada operação
Retornastring-array: uma resposta por operação, como texto

Restrições

1 ≤ ops.length ≤ 2000
words.length == ops.length
Cada ops[i] é insert, search ou startsWith.
1 ≤ words[i].length ≤ 20
words[i] contém apenas letras minúsculas do inglês.

Exemplos

Entrada: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Saída: ["null", "false", "true", "null", "true"]
Explicação: A princípio, somente card é armazenado, então buscar por car retorna "false": ele nunca foi inserido como uma palavra. Ele é o início de card, então startsWith car retorna "true". Depois que car é inserido, a busca o encontra.

Entrada: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Saída: ["null", "null", "true", "false", "false", "true", "true"]
Explicação: Ambas as palavras começam com te, então startsWith te é "true", mas nenhuma palavra é exatamente te, então a busca falha. Nenhuma palavra começa com tex. ten foi inserido, e tea é um prefixo de si mesma, então as duas últimas respostas são "true".

Entrada: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Saída: ["false", "false", "null", "true", "false", "true"]
Explicação: A trie começa vazia, então as duas primeiras respostas são "false". Depois que dog é inserido, a busca o encontra, nenhuma palavra começa com dogs, e do é o início de dog.

+16 testes ocultos ao enviar

Para ir além

Como você adicionaria uma operação countPrefix p que retorna quantas palavras distintas armazenadas começam com p, ainda em tempo O(L)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Um conjunto hash responde a search de imediato, mas startsWith pergunta sobre cada palavra que começa de determinada maneira, e um conjunto não tem noção de começos. Uma trie armazena os próprios começos: cada palavra é um caminho de letras a partir da raiz, palavras que começam igual compartilham o início de seu caminho, e uma flag em um nó marca onde termina uma palavra armazenada. Assim, ambas as perguntas exigem apenas percorrer no máximo L ligações, em que L é o comprimento da consulta, independentemente de quantas palavras estão armazenadas.

Mantenha uma lista de palavras e percorra-a

Intuição

Mantenha cada palavra inserida em uma lista. Para search w, compare w com cada palavra armazenada. Para startsWith p, verifique se alguma palavra armazenada começa com p. No segundo exemplo, startsWith te verifica primeiro tea e para ali; startsWith tex precisa verificar as duas palavras antes de responder "false".

Isso está correto e, com os limites definidos aqui, termina, mas cada consulta paga o custo de verificar todas as palavras armazenadas. Com n palavras armazenadas, uma consulta custa até n comparações de até L letras cada. 1.000 palavras armazenadas e 1.000 consultas resultam em um milhão de comparações de strings, e o trabalho continua aumentando com o dicionário. Nada é compartilhado: tea e ten armazenam cada uma seu próprio t e e.

Algoritmo

Comece com uma lista vazia de palavras.
Para insert w: acrescente w à lista.
Para search w: retorne se alguma palavra armazenada é igual a w.
Para startsWith p: retorne se alguma palavra armazenada começa com p.
Registre cada resposta como texto e retorne a lista.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

Uma trie: links para os nós filhos e uma flag de fim

Intuição

Cada nó de uma trie representa um prefixo: as letras no caminho da raiz até ele. A raiz representa o prefixo vazio. Um nó contém duas coisas: um link filho para cada letra que pode vir a seguir (um array de 26 posições ou um mapa de letra para nó) e uma flag, isEnd, que indica se uma palavra armazenada termina exatamente nesse nó.

insert percorre a palavra a partir da raiz. Para cada letra, segue o link filho, criando primeiro o nó se o link estiver ausente, e, na última letra, define isEnd. No segundo exemplo, inserir tea cria os nós para t, te e tea e marca tea. Inserir ten reutiliza t e te e adiciona apenas ten. As duas palavras compartilham o caminho para te, de onde vem o nome árvore de prefixos.

search e startsWith fazem o mesmo percurso sem criar nada. Se um link estiver ausente, nenhuma palavra armazenada começa com essas letras, então ambas retornam false: tex para no nó de te, que não tem um link para x. Se o percurso chegar ao fim, o nó em que ele para é o prefixo que você consultou. startsWith retorna true, e search retorna a flag desse nó. O nó de te existe, mas sua flag está desligada, porque as palavras que passam por ele terminam mais abaixo. Portanto, startsWith te é true e search te é false.

A flag é o que diferencia uma palavra de um prefixo. No primeiro exemplo, depois que card é inserida, o caminho c, a, r existe. Sem a flag, search car retornaria true incorretamente. Inserir car mais tarde não cria nenhum nó; apenas ativa a flag.

Cada operação segue no máximo L links, em que L é o comprimento da palavra, então seu custo é O(L), independentemente de quantas palavras estão armazenadas. A trie contém um nó por prefixo distinto, nunca mais do que o número total de letras inseridas.

Algoritmo

Defina um nó com links para os filhos (26 posições ou um mapa) e uma flag isEnd, e crie uma raiz vazia.
Para insert w: a partir da raiz, siga o link correspondente a cada letra de w, criando o nó quando o link estiver ausente. Defina isEnd no último nó.
Escreva uma função auxiliar find(p): a partir da raiz, siga o link correspondente a cada letra de p e desista assim que um link estiver ausente. Retorne o nó alcançado.
Para search w: responda true quando find(w) alcançar um nó cuja flag isEnd esteja definida.
Para startsWith p: responda true quando find(p) alcançar um nó.
Execute as operações em ordem e registre "null", "true" ou "false" para cada uma.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

Armadilhas e casos extremos

A maioria dos bugs surge da confusão entre “uma palavra termina aqui” e “uma palavra passa por aqui”.

Deixar que search responda true sempre que o caminho existir. Depois de inserir card, o caminho para car existe, mas car nunca foi inserida.
Definir isEnd somente nos nós recém-criados. Inserir card depois de cards não cria nada, mas o último nó ainda precisa da sua flag.
Criar um novo filho mesmo quando o link já existe. Isso desconecta tudo o que está armazenado abaixo dele: inserir ten com um novo nó t faz perder tea.
Esquecer que uma palavra é prefixo de si mesma. Depois de inserir tea, startsWith tea é true.
Continuar lendo além do fim do caminho. Um prefixo mais longo do que qualquer palavra, como sunny quando apenas sun está armazenada, deve parar no primeiro link ausente e responder false.
Retornar valores booleanos ou deixar de fora as inserções da resposta. Cada operação recebe uma string, incluindo "null" para uma inserção.

Perguntas frequentes4

Qual é a complexidade de tempo de uma trie?

Inserção, busca e startsWith seguem um link por letra do argumento, então cada uma leva O(L) de tempo para uma palavra de comprimento L, independentemente de quantas palavras estão armazenadas. A trie contém no máximo um nó por letra inserida, então o espaço é de O(T) nós para T letras inseridas no total, e cada nó armazena até 26 links de filhos.

Por que usar uma trie em vez de um conjunto hash?

Um conjunto hash responde a buscas de palavras completas em O(L), mas não consegue responder a uma consulta por prefixo sem percorrer todas as palavras. Você poderia adicionar um segundo conjunto com todos os prefixos de todas as palavras, mas uma palavra de 20 letras armazenaria então 20 prefixos com 210 letras ao todo. Uma trie armazena cada prefixo compartilhado uma única vez e responde às duas perguntas com o mesmo percurso. Com 26 posições de array por nó, um percurso abaixo de um prefixo também encontra as palavras em ordem alfabética, o que o preenchimento automático precisa.

Um nó de trie deve usar um array de 26 ligações ou um mapa de hash?

Um array oferece a busca mais rápida pelos filhos, com um índice por letra, mas cada nó paga o custo de 26 posições mesmo quando usa apenas uma. Um mapa armazena apenas os filhos existentes e funciona com qualquer alfabeto, ao custo de uma etapa de hash por letra. Para palavras em inglês em minúsculas, qualquer uma das opções serve; para texto Unicode ou tries esparsas, um mapa economiza muita memória.

Onde as tries são usadas na prática?

O preenchimento automático e as sugestões de pesquisa percorrem uma trie até o prefixo digitado e listam as palavras abaixo dele. Corretores ortográficos, jogos de palavras que procuram palavras do dicionário em um tabuleiro e roteadores que encontram o prefixo de endereço correspondente mais longo usam a mesma estrutura. Sempre que muitas strings compartilham o início e você faz consultas pelo início, uma trie é adequada.

Python

def trieOps(ops, words):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

Esperado

["null", "false", "true", "null", "true"]