Implement Trie (Prefix Tree)

Q: Warum einen Trie statt einer Hash-Menge verwenden?

Ein Hash-Set beantwortet Suchen nach ganzen Wörtern in O(L) , kann aber keine Präfixabfrage beantworten, ohne jedes Wort zu durchsuchen. Du könntest ein zweites Set hinzufügen, das jedes Präfix jedes Wortes enthält, aber ein 20 Buchstaben langes Wort speichert dann 20 Präfixe mit insgesamt 210 Buchstaben. Ein Trie speichert jedes gemeinsame Präfix nur einmal und beantwortet beide Fragen mit demselben Durchlauf. Mit 26 Array-Slots pro Knoten trifft ein Durchlauf unterhalb eines Präfixes auch auf die Wörter in alphabetischer Reihenfolge, was die Autovervollständigung benötigt.

MittelTrie

+10

Ein Trie oder Präfixbaum speichert Wörter so, dass Fragen nach ihren Anfängen schnell beantwortet werden. Erstelle einen für Wörter in Kleinbuchstaben mit drei Operationen: insert w fügt das Wort w hinzu, search w gibt an, ob w selbst eingefügt wurde, und startsWith p gibt an, ob ein eingefügtes Wort mit p beginnt. Ein Wort gilt als Präfix seiner selbst.

Du erhältst die Operationen der Reihe nach in ops, und words[i] ist das Wort oder Präfix für ops[i]. Führe sie auf einem einzigen, anfangs leeren Trie aus und gib für jede Operation einen String zurück: "null" für ein Einfügen und "true" oder "false" für eine Suche oder ein startsWith.

Funktion

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

opsstring-array: die Operationen in der Reihenfolge, in der sie ausgeführt werden
wordsstring-array: das Wort oder Präfix für jede Operation
Gibt zurückstring-array: eine Antwort pro Operation, als Text

Einschränkungen

1 ≤ ops.length ≤ 2000
words.length == ops.length
Jeder ops[i]-Wert ist insert, search oder startsWith.
1 ≤ words[i].length ≤ 20
words[i] enthält nur englische Kleinbuchstaben.

Beispiele

Eingabe: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Ausgabe: ["null", "false", "true", "null", "true"]
Erklärung: Zunächst wird nur card gespeichert, daher gibt die Suche nach car "false" zurück: Es wurde nie als Wort eingefügt. Es ist der Anfang von card, daher gibt startsWith car "true" zurück. Sobald car eingefügt wird, findet die Suche es.

Eingabe: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Ausgabe: ["null", "null", "true", "false", "false", "true", "true"]
Erklärung: Beide Wörter beginnen mit te, daher ist startsWith te "true", aber kein Wort ist genau te, daher schlägt die Suche fehl. Kein Wort beginnt mit tex. ten wurde eingefügt, und tea ist ein Präfix seiner selbst, daher lauten die letzten beiden Antworten "true".

Eingabe: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Ausgabe: ["false", "false", "null", "true", "false", "true"]
Erklärung: Der Trie ist zunächst leer, daher lauten die ersten beiden Antworten "false". Nachdem dog eingefügt wurde, findet die Suche es, kein Wort beginnt mit dogs, und do ist ein Präfix von dog.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du eine Operation countPrefix p hinzufügen, die zurückgibt, wie viele verschiedene gespeicherte Wörter mit p beginnen, und dabei weiterhin in O(L) Zeit läuft?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Hash-Set beantwortet search sofort, aber bei startsWith wird nach jedem Wort gefragt, das auf eine bestimmte Weise beginnt, und ein Set kennt keine Anfänge. Ein Trie speichert die Anfänge selbst: Jedes Wort ist ein Pfad aus Buchstaben von der Wurzel aus, Wörter mit gleichem Anfang teilen sich den Beginn ihres Pfads, und eine Markierung an einem Knoten zeigt an, wo ein gespeichertes Wort endet. Beide Fragen erfordern dann jeweils einen Durchlauf über höchstens L Verknüpfungen, wobei L die Länge der Suchanfrage ist – unabhängig davon, wie viele Wörter gespeichert sind.

Führe eine Wortliste und durchsuche sie

Idee

Behalte jedes eingefügte Wort in einer Liste. Vergleiche bei search w w mit jedem gespeicherten Wort. Prüfe bei startsWith p, ob ein gespeichertes Wort mit p beginnt. Im zweiten Beispiel betrachtet startsWith te zuerst tea und hört dort auf; startsWith tex muss sich beide Wörter ansehen, bevor es "false" zurückgibt.

Das ist korrekt, und mit den hier geltenden Grenzen wird die Abfrage abgeschlossen, aber jede Abfrage kostet für jedes gespeicherte Wort Aufwand. Bei n gespeicherten Wörtern kostet eine Abfrage bis zu n Vergleiche mit jeweils bis zu L Buchstaben. 1,000 gespeicherte Wörter und 1,000 Abfragen ergeben eine Million Zeichenkettenvergleiche, und der Aufwand wächst weiter mit dem Wörterbuch. Außerdem wird nichts gemeinsam genutzt: tea und ten speichern jeweils ihr eigenes t und e.

Algorithmus

Beginne mit einer leeren Wortliste.
Für insert w: Füge w zur Liste hinzu.
Für search w: Gib zurück, ob ein gespeichertes Wort gleich w ist.
Für startsWith p: Gib zurück, ob ein gespeichertes Wort mit p beginnt.
Halte jede Antwort als Text fest und gib die Liste zurück.

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

Ein Trie: Verknüpfungen zu Kindknoten und ein Endkennzeichen

Idee

Jeder Knoten eines Tries steht für ein Präfix: die Buchstaben auf dem Pfad von der Wurzel bis zu diesem Knoten. Die Wurzel steht für das leere Präfix. Ein Knoten enthält zwei Dinge: eine Kind-Verknüpfung für jeden Buchstaben, der als Nächstes kommen kann (ein Array mit 26 Plätzen oder eine Zuordnung von Buchstaben zu Knoten) und ein Flag, isEnd, das angibt, ob ein gespeichertes Wort genau an diesem Knoten endet.

insert durchläuft das Wort von der Wurzel aus. Für jeden Buchstaben folgt es der Kind-Verknüpfung und erstellt zuerst den Knoten, falls die Verknüpfung fehlt. Beim letzten Buchstaben setzt es isEnd. Im zweiten Beispiel erstellt das Einfügen von tea die Knoten für t, te und tea und markiert tea. Beim Einfügen von ten werden t und te wiederverwendet und nur ten hinzugefügt. Die beiden Wörter teilen sich den Pfad für te; daher stammt die Bezeichnung Präfixbaum.

search und startsWith durchlaufen denselben Pfad, ohne etwas zu erstellen. Fehlt eine Verknüpfung, beginnt kein gespeichertes Wort mit diesen Buchstaben, also geben beide false zurück: tex hält beim Knoten für te an, der keine x-Verknüpfung hat. Erreicht der Durchlauf das Ende, ist der Knoten, bei dem er angekommen ist, das abgefragte Präfix. startsWith gibt true zurück, und search gibt das Flag dieses Knotens zurück. Der Knoten für te existiert, aber sein Flag ist ausgeschaltet, weil die Wörter, die durch ihn verlaufen, weiter unten enden. Also ist startsWith te true und search te false.

Das Flag unterscheidet ein Wort von einem Präfix. Im ersten Beispiel ist der Pfad c, a, r vorhanden, nachdem card eingefügt wurde. Ohne das Flag würde search car fälschlicherweise true zurückgeben. Das spätere Einfügen von car erstellt überhaupt keinen Knoten; es schaltet lediglich das Flag ein.

Jede Operation folgt höchstens L Verknüpfungen, wobei L die Länge des Wortes ist. Daher kostet sie O(L), unabhängig davon, wie viele Wörter gespeichert sind. Der Trie enthält einen Knoten pro eindeutigem Präfix, niemals mehr als die Gesamtzahl der eingefügten Buchstaben.

Algorithmus

Definiere einen Knoten mit Verknüpfungen zu seinen Kindern (26 Plätze oder eine Map) und einem isEnd-Flag und erstelle eine leere Wurzel.
Für insert w: Folge von der Wurzel aus der Verknüpfung für jeden Buchstaben von w und erstelle den Knoten, wenn die Verknüpfung fehlt. Setze isEnd beim letzten Knoten.
Schreibe eine Hilfsfunktion find(p): Folge von der Wurzel aus der Verknüpfung für jeden Buchstaben von p und brich sofort ab, sobald eine fehlt. Gib den erreichten Knoten zurück.
Für search w: Antworte mit true, wenn find(w) einen Knoten erreicht, bei dem isEnd gesetzt ist.
Für startsWith p: Antworte mit true, wenn find(p) einen Knoten erreicht.
Führe die Operationen der Reihe nach aus und notiere für jede "null", "true" oder "false".

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

Stolperfallen und Grenzfälle

Die meisten Fehler entstehen dadurch, dass man „ein Wort endet hier“ mit „ein Wort führt hier hindurch“ verwechselt.

search immer dann true zurückgeben lassen, wenn der Pfad existiert. Nach dem Einfügen von card existiert der Pfad für car, aber car wurde nie eingefügt.
isEnd nur bei neu erstellten Knoten setzen. Beim Einfügen von card nach cards wird nichts erstellt, doch der letzte Knoten benötigt trotzdem sein Flag.
Einen neuen Kindknoten erstellen, selbst wenn die Verknüpfung bereits existiert. Dadurch geht alles verloren, was darunter gespeichert ist: Beim Einfügen von ten mit einem neuen t-Knoten geht tea verloren.
Vergessen, dass ein Wort ein Präfix von sich selbst ist. Nach dem Einfügen von tea ist startsWith tea true.
Über das Ende des Pfads hinauslesen. Ein Präfix, das länger als jedes Wort ist, wie sunny, wenn nur sun gespeichert ist, muss beim ersten fehlenden Link abbrechen und false zurückgeben.
Boolesche Werte zurückgeben oder Einfügevorgänge in der Antwort auslassen. Jede Operation erhält einen String, einschließlich "null" für ein Einfügen.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität eines Tries?

Insert, search und startsWith folgen jeweils einer Verknüpfung pro Buchstabe ihres Arguments. Daher benötigen sie für ein Wort der Länge L jeweils O(L) Zeit, unabhängig davon, wie viele Wörter gespeichert sind. Der Trie enthält höchstens einen Knoten pro eingefügtem Buchstaben. Daher benötigt er für insgesamt T eingefügte Buchstaben O(T) Knoten, und jeder Knoten speichert bis zu 26 untergeordnete Verknüpfungen.

Warum einen Trie statt einer Hash-Menge verwenden?

Ein Hash-Set beantwortet Suchen nach ganzen Wörtern in O(L), kann aber keine Präfixabfrage beantworten, ohne jedes Wort zu durchsuchen. Du könntest ein zweites Set hinzufügen, das jedes Präfix jedes Wortes enthält, aber ein 20 Buchstaben langes Wort speichert dann 20 Präfixe mit insgesamt 210 Buchstaben. Ein Trie speichert jedes gemeinsame Präfix nur einmal und beantwortet beide Fragen mit demselben Durchlauf. Mit 26 Array-Slots pro Knoten trifft ein Durchlauf unterhalb eines Präfixes auch auf die Wörter in alphabetischer Reihenfolge, was die Autovervollständigung benötigt.

Sollte ein Trie-Knoten ein Array mit 26 Verweisen oder eine Hash-Map verwenden?

Ein Array ermöglicht den schnellsten Zugriff auf ein Kind, mit einem Index pro Buchstabe, aber jeder Knoten belegt 26 Plätze, selbst wenn er nur einen verwendet. Eine Map speichert nur die vorhandenen Kinder und funktioniert für jedes Alphabet, allerdings ist pro Buchstabe ein zusätzlicher Hashing-Schritt erforderlich. Für englische Wörter in Kleinbuchstaben sind beide Optionen geeignet; für Unicode-Text oder dünn besetzte Tries spart eine Map viel Speicher.

Wo werden Tries in der Praxis verwendet?

Autovervollständigung und Suchvorschläge durchlaufen einen Trie bis zum eingegebenen Präfix und listen die darunterliegenden Wörter auf. Rechtschreibprüfungen, Wortspiele, die ein Spielfeld nach Wörterbucheinträgen durchsuchen, und Router, die das längste passende Adresspräfix finden, verwenden dieselbe Struktur. Immer wenn viele Zeichenfolgen denselben Anfang haben und du nach diesem Anfang suchst, eignet sich ein Trie.

Python

def trieOps(ops, words):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

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