Implement Trie (Prefix Tree)

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

Un insieme hash trova parole intere in O(L) , ma non può rispondere a una domanda sui prefissi senza esaminare ogni parola. Memorizzare ogni prefisso in un secondo insieme costa 210 lettere per una singola parola di 20 lettere. Un trie memorizza ogni prefisso condiviso una sola volta e risponde a entrambe le domande con un'unica visita.

MedioTrie

+10

Crea un trie (albero di prefissi) per parole in minuscolo con tre operazioni: insert w aggiunge la parola w, search w indica se w stessa è stata inserita e startsWith p indica se qualche parola inserita inizia con p. Una parola è considerata prefisso di se stessa.

L'operazione i è ops[i] su words[i]. Esegui le operazioni nell'ordine indicato su un trie vuoto e restituisci una stringa per ciascuna: "null" per un inserimento, "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 minuscole inglesi.

Esempi

Input: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Output: ["null", "false", "true", "null", "true"]
Spiegazione: car è all’inizio di card, quindi startsWith car è "true", ma car non è mai stato inserito, quindi la prima ricerca restituisce "false". Dopo insert 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, ma nessuna delle due è esattamente te, quindi startsWith è "true" e search è "false". Nessuna parola inizia con tex e tea è un prefisso di sé stessa.

Input: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Output: ["false", "false", "null", "true", "false", "true"]
Spiegazione: Nel trie vuoto entrambe le query restituiscono "false". Dopo insert dog, la ricerca lo trova, nessuna parola inizia con dogs e do è l'inizio di dog.

Per approfondire

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

Suggerimenti

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

0 di 3 aperti

Soluzione

Un insieme hash risponde a search, ma non ha nozione di inizi, quindi startsWith dovrebbe esaminare ogni parola. Un trie memorizza ogni parola come un percorso di lettere dalla radice: le parole che iniziano allo stesso modo condividono un percorso, e un flag indica dove termina una parola memorizzata. Entrambe le query diventano una sola visita di al massimo L collegamenti.

Conserva un elenco di parole e scansionalo

Intuizione

Mantieni ogni parola inserita in un elenco. search w confronta w con ogni parola memorizzata, e startsWith p verifica se una qualsiasi parola memorizzata inizia con p. È corretto perché verifica direttamente la definizione. Con n parole memorizzate, ogni query richiede fino a n confronti di un massimo di L lettere: 1.000 parole e 1.000 query comportano un milione di confronti tra stringhe.

Algoritmo

Inizia con una lista vuota.
insert w: aggiungi w in fondo.
search w: restituisci se una delle parole memorizzate è uguale a w.
startsWith p: restituisci se una delle parole memorizzate inizia con 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

Un trie: collegamenti ai nodi figli e un flag di fine

Intuizione

Ogni nodo rappresenta un prefisso: le lettere sul percorso dalla radice fino a esso. Contiene un collegamento figlio per ogni lettera che può seguire (26 posizioni o una mappa) e un flag isEnd che indica se una parola memorizzata termina esattamente lì. Inserire tea crea i nodi per t, te e tea; inserire ten aggiunge poi solo ten, perché le due parole condividono il percorso per te.

Un percorso che incontra un collegamento mancante dimostra che nessuna parola memorizzata inizia con quelle lettere: tex si ferma a te, che non ha un collegamento x. Un percorso che raggiunge la fine si trova sul nodo della query, quindi startsWith è true e search risponde con il flag. Il nodo per te esiste, ma il suo flag è disattivato, quindi search te è false. Ogni operazione segue al massimo L collegamenti, indipendentemente dal numero di parole memorizzate, e il trie contiene un nodo per ogni prefisso distinto.

Algoritmo

Crea una radice senza collegamenti figli e con isEnd disattivato.
insert w: dalla radice, segui il collegamento per ogni lettera, creando il nodo quando manca. Imposta isEnd sull'ultimo nodo.
find(p): dalla radice, segui il collegamento per ogni lettera; non restituire nulla non appena ne manca uno, altrimenti restituisci il nodo raggiunto.
search w: true quando find(w) restituisce un nodo con isEnd impostato.
startsWith p: true quando find(p) restituisce un nodo.

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

Lasciare che search restituisca true ogni volta che il percorso esiste. Dopo insert card, il percorso per car esiste, ma search car deve essere false.
Impostare isEnd solo sui nodi appena creati. Inserire card dopo cards non crea nulla, eppure l’ultimo nodo ha bisogno del suo flag.
Creare un nuovo figlio quando il collegamento esiste già. Inserire ten con un nuovo nodo t fa perdere tea.
Proseguire oltre la fine del percorso. startsWith sunny con solo sun memorizzato deve fermarsi al primo collegamento mancante e restituire false.

Domande frequenti3

Qual è la complessità temporale di un trie?

Inserimento, ricerca e startsWith seguono ciascuno un collegamento per lettera, quindi richiedono O(L) per una parola di lunghezza L, indipendentemente dal numero di parole memorizzate. Lo spazio è di O(T) nodi per T lettere inserite in totale, con ogni nodo che contiene fino a 26 collegamenti ai figli.

Perché usare un trie invece di un insieme hash?

Un insieme hash trova parole intere in O(L), ma non può rispondere a una domanda sui prefissi senza esaminare ogni parola. Memorizzare ogni prefisso in un secondo insieme costa 210 lettere per una singola parola di 20 lettere. Un trie memorizza ogni prefisso condiviso una sola volta e risponde a entrambe le domande con un'unica visita.

Dovrebbe un nodo del trie usare un array di 26 collegamenti o una mappa hash?

Un array trova un figlio con un indice, ma occupa 26 slot per nodo, anche per un nodo con un solo figlio. Una mappa memorizza solo i figli esistenti e funziona con qualsiasi alfabeto, al costo di un hash per lettera. Per l’inglese in minuscolo vanno bene entrambe; per Unicode o trie sparsi, una mappa fa risparmiare memoria.

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

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

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