Implement Trie (Prefix Tree)

Q: Perché usare un trie invece di un insieme hash?

Un insieme hash risponde alle ricerche di parole intere in O(L) , ma non può rispondere a una domanda sui prefissi senza esaminare ogni parola. Potresti aggiungere un secondo insieme che contenga ogni prefisso di ogni parola, ma una parola di 20 lettere memorizzerebbe allora 20 prefissi per un totale di 210 lettere. Un trie memorizza ogni prefisso condiviso una sola volta e risponde a entrambe le domande con la stessa visita. Con 26 posizioni nell'array per nodo, anche una visita sotto un prefisso incontra le parole in ordine alfabetico, cosa necessaria per il completamento automatico.

MedioTrie

+10

Un trie, o albero dei prefissi, memorizza le parole in modo da rispondere rapidamente alle domande sui loro inizi. Costruiscine uno per parole in minuscolo con tre operazioni: insert w aggiunge la parola w, search w indica se w è stata inserita, e startsWith p indica se qualche parola inserita inizia con p. Una parola è considerata prefisso di sé stessa.

Ricevi le operazioni in ordine in ops, e words[i] è la parola o il prefisso per ops[i]. Eseguile su un unico trie inizialmente vuoto e restituisci una stringa per ogni operazione: "null" per un inserimento e "true" o "false" per una ricerca o un'operazione startsWith.

Funzione

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

opsstring-array: le operazioni, nell’ordine in cui vengono eseguite
wordsstring-array: la parola o il prefisso per ogni operazione
Restituiscestring-array: una risposta per operazione, come testo

Vincoli

1 ≤ ops.length ≤ 2000
words.length == ops.length
Ogni ops[i] è insert, search o startsWith.
1 ≤ words[i].length ≤ 20
words[i] contiene solo lettere inglesi minuscole.

Esempi

Input: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Output: ["null", "false", "true", "null", "true"]
Spiegazione: All'inizio è memorizzato solo card, quindi cercando car si ottiene "false": non è mai stato inserito come parola. È l'inizio di card, quindi startsWith car restituisce "true". Una volta inserito car, la ricerca lo trova.

Input: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Output: ["null", "null", "true", "false", "false", "true", "true"]
Spiegazione: Entrambe le parole iniziano con te, quindi startsWith te è "true", ma nessuna parola è esattamente te, quindi la ricerca non riesce. Nessuna parola inizia con tex. ten è stato inserito e tea è un prefisso di sé stesso, quindi le ultime due risposte sono "true".

Input: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Output: ["false", "false", "null", "true", "false", "true"]
Spiegazione: Il trie è inizialmente vuoto, quindi le prime due risposte sono "false". Dopo aver inserito dog, la ricerca lo trova, nessuna parola inizia con dogs e do è l'inizio di dog.

+16 test nascosti all’invio

Per approfondire

Come aggiungeresti un'operazione countPrefix p che restituisca quante parole distinte memorizzate iniziano con p, sempre in tempo O(L)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Un insieme hash risponde immediatamente a search, ma startsWith riguarda ogni parola che inizia in un certo modo, e un insieme non ha il concetto di inizio. Un trie memorizza gli inizi stessi: ogni parola è un percorso di lettere dalla radice, le parole che iniziano allo stesso modo condividono l'inizio del loro percorso e un flag su un nodo indica dove termina una parola memorizzata. Entrambe le domande richiedono quindi un'unica visita di al massimo L collegamenti, dove L è la lunghezza della query, indipendentemente dal numero di parole memorizzate.

Mantieni un elenco di parole e analizzalo

Intuizione

Mantieni ogni parola inserita in un elenco. Per search w, confronta w con ogni parola memorizzata. Per startsWith p, verifica se una qualsiasi parola memorizzata inizia con p. Nel secondo esempio, startsWith te controlla prima tea e si ferma lì; startsWith tex deve controllare entrambe le parole prima di rispondere "false".

Questo è corretto e, con i limiti indicati qui, termina, ma ogni query richiede di esaminare tutte le parole memorizzate. Con n parole memorizzate, una query comporta fino a n confronti di un massimo di L lettere ciascuno. 1.000 parole memorizzate e 1.000 query comportano un milione di confronti tra stringhe, e il lavoro continua a crescere insieme al dizionario. Inoltre non si condivide nulla: tea e ten memorizzano ciascuna la propria t e la propria e.

Algoritmo

Inizia con un elenco di parole vuoto.
Per insert w: aggiungi w all'elenco.
Per search w: restituisci se una delle parole memorizzate è uguale a w.
Per startsWith p: restituisci se una delle parole memorizzate inizia con p.
Registra ogni risposta come testo e restituisci l'elenco.

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

Un trie: collegamenti ai figli e un flag di fine

Intuizione

Ogni nodo di un trie rappresenta un prefisso: le lettere sul percorso dalla radice fino a esso. La radice rappresenta il prefisso vuoto. Un nodo contiene due cose: un collegamento figlio per ogni lettera che può seguire (un array di 26 posizioni oppure una mappa da lettera a nodo) e un indicatore, isEnd, che specifica se una parola memorizzata termina esattamente in questo nodo.

insert percorre la parola partendo dalla radice. Per ogni lettera segue il collegamento figlio, creando prima il nodo se il collegamento manca, e sull'ultima lettera imposta isEnd. Nel secondo esempio, inserire tea crea i nodi per t, te e tea e contrassegna tea. Inserire ten riutilizza t e te e aggiunge solo ten. Le due parole condividono il percorso per te, da cui deriva il nome albero dei prefissi.

search e startsWith eseguono lo stesso percorso senza creare nulla. Se manca un collegamento, nessuna parola memorizzata inizia con quelle lettere, quindi entrambe restituiscono false: tex si ferma al nodo per te, che non ha un collegamento per x. Se il percorso raggiunge la fine, il nodo in cui si trova corrisponde al prefisso richiesto. startsWith restituisce true, mentre search restituisce il valore dell'indicatore di quel nodo. Il nodo per te esiste, ma il suo indicatore è disattivato, perché le parole che lo attraversano terminano più in basso. Quindi startsWith te restituisce true e search te restituisce false.

L'indicatore è ciò che distingue una parola da un prefisso. Nel primo esempio, dopo aver inserito card, esiste il percorso c, a, r. Senza l'indicatore, search car restituirebbe erroneamente true. Inserire car in seguito non crea alcun nodo; attiva soltanto l'indicatore.

Ogni operazione segue al massimo L collegamenti, dove L è la lunghezza della parola, quindi ha un costo di O(L) indipendentemente dal numero di parole memorizzate. Il trie contiene un nodo per ogni prefisso distinto, mai più del numero totale di lettere inserite.

Algoritmo

Definisci un nodo con collegamenti ai figli (26 slot o una mappa) e un flag isEnd, e crea una radice vuota.
Per insert w: dalla radice, segui il collegamento per ogni lettera di w, creando il nodo quando manca il collegamento. Imposta isEnd sull'ultimo nodo.
Scrivi una funzione helper find(p): dalla radice, segui il collegamento per ogni lettera di p e fermati appena ne manca uno. Restituisci il nodo raggiunto.
Per search w: rispondi true quando find(w) raggiunge un nodo il cui isEnd è impostato.
Per startsWith p: rispondi true quando find(p) raggiunge un nodo.
Esegui le operazioni in ordine e registra "null", "true" o "false" per ciascuna.

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

Trappole e casi limite

La maggior parte dei bug deriva dal confondere «qui finisce una parola» con «qui passa una parola».

Far sì che search risponda true ogni volta che il percorso esiste. Dopo aver inserito card, il percorso per car esiste, ma car non è mai stato inserito.
Impostare isEnd solo sui nodi appena creati. Inserire card dopo cards non crea nulla, ma l’ultimo nodo ha comunque bisogno del suo flag.
Creare un nuovo figlio anche quando il collegamento esiste. Questo interrompe l’accesso a tutto ciò che è memorizzato sotto: inserire ten con un nuovo nodo t fa perdere tea.
Dimenticare che una parola è prefisso di se stessa. Dopo aver inserito tea, startsWith tea è true.
Continuare a leggere oltre la fine del percorso. Un prefisso più lungo di qualsiasi parola, come sunny quando è memorizzato solo sun, deve fermarsi al primo collegamento mancante e rispondere false.
Restituire valori booleani o omettere gli inserimenti dalla risposta. Ogni operazione produce una stringa, incluso "null" per un inserimento.

Domande frequenti4

Qual è la complessità temporale di un trie?

Insert, search e startsWith seguono ciascuna un collegamento per ogni lettera del rispettivo argomento, quindi ognuna richiede un tempo O(L) per una parola di lunghezza L, indipendentemente dal numero di parole memorizzate. Il trie contiene al massimo un nodo per ogni lettera inserita, quindi lo spazio è di O(T) nodi per T lettere inserite in totale, e ogni nodo memorizza fino a 26 collegamenti ai figli.

Perché usare un trie invece di un insieme hash?

Un insieme hash risponde alle ricerche di parole intere in O(L), ma non può rispondere a una domanda sui prefissi senza esaminare ogni parola. Potresti aggiungere un secondo insieme che contenga ogni prefisso di ogni parola, ma una parola di 20 lettere memorizzerebbe allora 20 prefissi per un totale di 210 lettere. Un trie memorizza ogni prefisso condiviso una sola volta e risponde a entrambe le domande con la stessa visita. Con 26 posizioni nell'array per nodo, anche una visita sotto un prefisso incontra le parole in ordine alfabetico, cosa necessaria per il completamento automatico.

Un nodo di un trie dovrebbe usare un array di 26 collegamenti o una mappa hash?

Un array consente la ricerca dei figli più rapida, con un indice per ogni lettera, ma ogni nodo occupa spazio per 26 posizioni anche quando ne usa una sola. Una mappa memorizza solo i figli esistenti e funziona con qualsiasi alfabeto, al costo di un'operazione di hashing per ogni lettera. Per le parole inglesi in minuscolo vanno bene entrambe; per il testo Unicode o per i trie sparsi, una mappa consente di risparmiare molta memoria.

Dove si usano i tentativi nella pratica?

Il completamento automatico e i suggerimenti di ricerca percorrono un trie fino al prefisso digitato ed elencano le parole che si trovano sotto di esso. I correttori ortografici, i giochi di parole che cercano parole del dizionario su una griglia e i router che individuano il prefisso di indirizzo corrispondente più lungo usano la stessa struttura. Ogni volta che molte stringhe condividono le stesse iniziali e fai ricerche in base alle iniziali, un trie è la scelta giusta.

Python

def trieOps(ops, words):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

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