Implement Trie (Prefix Tree)

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

Um conjunto hash encontra palavras inteiras em O(L) , mas não consegue responder a uma consulta de prefixo sem percorrer todas as palavras. Armazenar cada prefixo em um segundo conjunto custa 210 letras para uma única palavra de 20 letras. Uma trie armazena cada prefixo compartilhado uma única vez e responde às duas perguntas com uma única percorrida.

MédioTrie

+10

Construa uma trie (árvore de prefixos) 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.

A operação i é ops[i] aplicada a words[i]. Execute-as em ordem em uma trie vazia e retorne uma string para cada uma: "null" para uma inserção, "true" ou "false" para uma busca ou uma 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: car começa com card, então startsWith car é "true", mas car nunca foi inserido, então a primeira busca retorna "false". Depois de insert car, 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, mas nenhuma é exatamente te, então startsWith é "true" e search é "false". Nenhuma palavra começa com tex, e tea é um prefixo de si mesma.

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: Na trie vazia, ambas as consultas são "false". Após insert dog, a busca o encontra, nenhuma palavra começa com dogs, e do é o início de dog.

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, mas não tem noção de início, então startsWith percorreria todas as palavras. Uma trie armazena cada palavra como um caminho de letras a partir da raiz: palavras que começam igual compartilham um caminho, e uma flag marca onde uma palavra armazenada termina. Ambas as consultas se tornam uma única travessia de no máximo L ligações.

Mantenha uma lista de palavras e percorra-a

Intuição

Mantenha cada palavra inserida em uma lista. search w compara w com cada palavra armazenada, e startsWith p verifica se alguma palavra armazenada começa com p. Isso está correto porque testa diretamente a definição. Com n palavras armazenadas, cada consulta custa até n comparações de até L letras: 1.000 palavras e 1.000 consultas resultam em um milhão de comparações de strings.

Algoritmo

Comece com uma lista vazia.
insert w: adicione w ao final.
search w: retorne se alguma palavra armazenada é igual a w.
startsWith p: retorne se alguma palavra armazenada começa com p.

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 filhos e uma flag de término

Intuição

Cada nó representa um prefixo: as letras no caminho da raiz até ele. Ele contém um link para cada letra que pode vir em seguida (26 posições ou um mapa) e uma sinalização isEnd que indica se uma palavra armazenada termina exatamente ali. Inserir tea cria os nós para t, te e tea; inserir ten em seguida adiciona apenas ten, porque as duas palavras compartilham o caminho de te.

Um percurso que encontra um link ausente prova que nenhuma palavra armazenada começa com essas letras: tex para em te, que não tem um link para x. Um percurso que chega ao fim está no nó da consulta, então startsWith é verdadeiro e search responde com a sinalização. O nó de te existe, mas sua sinalização está desligada, então search te é falso. Cada operação percorre no máximo L links, independentemente de quantas palavras estão armazenadas, e a trie contém um nó por prefixo distinto.

Algoritmo

Crie uma raiz sem links filhos e com isEnd desativado.
insert w: a partir da raiz, siga o link de cada letra, criando o nó quando ele não existir. Ative isEnd no último nó.
find(p): a partir da raiz, siga o link de cada letra; não retorne nada assim que algum estiver faltando; caso contrário, retorne o nó alcançado.
search w: verdadeiro quando find(w) retorna um nó com isEnd ativado.
startsWith p: verdadeiro quando find(p) retorna um nó.

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

Fazer com que search retorne true sempre que o caminho existir. Após insert card, o caminho para car existe, mas search car deve retornar false.
Definir isEnd somente em nós recém-criados. Inserir card depois de cards não cria nada, mas o último nó precisa dessa flag.
Criar um novo filho quando o link já existe. Inserir ten com um novo nó t faz com que tea seja perdido.
Continuar a leitura depois do fim do caminho. startsWith sunny com apenas sun armazenado deve parar no primeiro link ausente e retornar false.

Perguntas frequentes3

Qual é a complexidade de tempo de uma trie?

A inserção, a busca e startsWith seguem um link por letra, então cada uma leva O(L) para uma palavra de comprimento L, independentemente de quantas palavras estão armazenadas. O espaço é de O(T) nós para T letras inseridas no total, cada nó contendo até 26 links filhos.

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

Um conjunto hash encontra palavras inteiras em O(L), mas não consegue responder a uma consulta de prefixo sem percorrer todas as palavras. Armazenar cada prefixo em um segundo conjunto custa 210 letras para uma única palavra de 20 letras. Uma trie armazena cada prefixo compartilhado uma única vez e responde às duas perguntas com uma única percorrida.

Um nó de trie deve usar um array de 26 links ou um mapa hash?

Um array encontra um filho com um índice, mas custa 26 posições por nó, mesmo para um nó com um único filho. Um mapa armazena apenas os filhos existentes e funciona com qualquer alfabeto, ao custo de um hash por letra. Para o inglês em letras minúsculas, ambos funcionam; para Unicode ou tries esparsas, um mapa economiza memória.

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

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

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