Implement Trie (Prefix Tree)
Erstelle einen Trie (Präfixbaum) 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.
Die Operation i ist ops[i] für words[i]. Führe sie der Reihe nach in einem leeren Trie aus und gib jeweils einen String zurück: "null" für ein Einfügen, "true" oder "false" für eine Suche oder ein startsWith.
Funktion
- 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 ≤ 2000words.length == ops.length- Jedes
ops[i]istinsert,searchoderstartsWith. 1 ≤ words[i].length ≤ 20words[i]enthält ausschließlich kleingeschriebene englische Buchstaben.
Beispiele
- Eingabe
- ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
- Ausgabe
- ["null", "false", "true", "null", "true"]
- Erklärung
carbeginntcard, also iststartsWith car"true", abercarwurde nie eingefügt, daher ist die erste Suche"false". Nachinsert carfindet 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, aber keines ist genaute, daher ist startsWith"true"und search"false". Kein Wort beginnt mittex, undteaist ein Präfix seiner selbst.
- Eingabe
- ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
- Ausgabe
- ["false", "false", "null", "true", "false", "true"]
- Erklärung
- Beim leeren Trie sind beide Abfragen
"false". Nachinsert dogfindet die Suche es, kein Wort beginnt mitdogs, unddobeginnt mitdog.
Weiterführende Frage
Wie würdest du eine countPrefix p-Operation hinzufügen, die zurückgibt, wie viele verschiedene gespeicherte Wörter mit p beginnen, und das weiterhin in O(L)-Zeit?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Eine Menge ganzer Wörter beantwortet
searchmit einer einzigen Suche, aber sie kann dir nicht sagen, ob ein Wort mittebeginnt, ohne jedes einzelne zu überprüfen. Was wäre, wenn Wörter, die gleich beginnen, den Speicherplatz für diesen Anfang gemeinsam nutzen würden?Erstelle einen Baum, in dem jeder Knoten für ein Präfix steht und für jeden Buchstaben, der als Nächstes kommen kann, eine Kindverbindung hat. Ein Wort ist dann ein Pfad von der Wurzel aus. Gib jedem Knoten ein Flag, das angibt, ob genau dort ein gespeichertes Wort endet.
Jeder Vorgang durchläuft die Buchstaben ausgehend von der Wurzel.
inserterstellt die fehlenden Knoten und setzt das Flag auf dem letzten Knoten.startsWithist erfolgreich, wenn der Durchlauf das Ende erreicht;searchbenötigt außerdem das Flag auf dem Knoten, an dem es stoppt.
Lösung
Ein Hash-Set beantwortet search, kennt aber keine Anfänge, daher würde startsWith jedes Wort durchsuchen. Ein Trie speichert jedes Wort als Pfad aus Buchstaben von der Wurzel aus: Wörter, die gleich beginnen, teilen sich einen Pfad, und ein Flag markiert, wo ein gespeichertes Wort endet. Beide Abfragen erfordern nur einen einzigen Durchlauf mit höchstens L Verknüpfungen.
Behalte eine Liste mit Wörtern und durchsuche sie
Idee
Bewahre jedes eingefügte Wort in einer Liste auf. search w vergleicht w mit jedem gespeicherten Wort, und startsWith p prüft, ob ein gespeichertes Wort mit p beginnt. Das ist korrekt, weil es die Definition direkt testet. Bei n gespeicherten Wörtern kostet jede Abfrage bis zu n Vergleiche von jeweils bis zu L Buchstaben: 1.000 Wörter und 1.000 Abfragen ergeben eine Million Zeichenfolgenvergleiche.
Algorithmus
- Beginne mit einer leeren Liste.
insert w: fügewhinzu.search w: gib zurück, ob ein gespeichertes Wort gleichwist.startsWith p: gib zurück, ob ein gespeichertes Wort mitpbeginnt.
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 resultEin Trie: Verknüpfungen zu Kindknoten und ein End-Flag
Idee
Jeder Knoten steht für ein Präfix, also die Buchstaben auf dem Pfad von der Wurzel zu diesem Knoten. Er enthält für jeden Buchstaben, der als Nächstes folgen kann, eine Verknüpfung zu einem Kindknoten (26 Plätze oder eine Map) sowie ein Flag isEnd, das angibt, ob ein gespeichertes Wort genau dort endet. Beim Einfügen von tea werden die Knoten für t, te und tea erstellt; beim anschließenden Einfügen von ten kommt nur ten hinzu, da sich die beiden Wörter den Pfad für te teilen.
Ein Durchlauf, der auf eine fehlende Verknüpfung trifft, beweist, dass kein gespeichertes Wort mit diesen Buchstaben beginnt: tex endet bei te, wo es keine x-Verknüpfung gibt. Erreicht ein Durchlauf das Ende, steht er auf dem Knoten für die Abfrage. Daher ist startsWith wahr und search gibt den Wert des Flags zurück. Der Knoten für te existiert, aber sein Flag ist nicht gesetzt, also ist search te falsch. Jeder Vorgang folgt höchstens L Verknüpfungen, unabhängig davon, wie viele Wörter gespeichert sind, und der Trie enthält einen Knoten pro eindeutigem Präfix.
Algorithmus
- Erstelle eine Wurzel ohne Kindverknüpfungen und mit deaktiviertem
isEnd. insert w: Folge von der Wurzel aus der Verknüpfung für jeden Buchstaben und erstelle den Knoten, wenn er fehlt. SetzeisEndbeim letzten Knoten.find(p): Folge von der Wurzel aus der Verknüpfung für jeden Buchstaben; gib nichts zurück, sobald eine Verknüpfung fehlt, andernfalls den erreichten Knoten.search w: true, wennfind(w)einen Knoten zurückgibt, bei demisEndgesetzt ist.startsWith p: true, wennfind(p)einen Knoten zurückgibt.
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
searchimmer dann true zurückgeben lassen, wenn der Pfad existiert. Nachinsert cardexistiert der Pfad fürcar, abersearch carmuss false ergeben.isEndnur bei neu erstellten Knoten setzen. Beim Einfügen voncardnachcardswird nichts erstellt, aber der letzte Knoten braucht sein Flag.- Ein neues Kind erstellen, obwohl der Link bereits existiert. Beim Einfügen von
tenmit einem neuent-Knoten gehtteaverloren. - Über das Ende des Pfads hinauslesen.
startsWith sunnymuss bei nur gespeichertemsunam ersten fehlenden Link anhalten und false ergeben.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität eines Tries?
Einfügen, Suchen und startsWith folgen jeweils einem Link pro Buchstabe, daher benötigt jeder Vorgang für ein Wort der Länge O(L), unabhängig davon, wie viele Wörter gespeichert sind. Der Speicherplatzbedarf beträgt O(T) Knoten für insgesamt T eingefügte Buchstaben, wobei jeder Knoten bis zu 26 untergeordnete Links enthält.
Warum einen Trie statt einer Hash-Menge verwenden?
Ein Hash-Set findet ganze Wörter in O(L), kann aber eine Präfixfrage nicht beantworten, ohne jedes Wort zu durchsuchen. Jedes Präfix in einem zweiten Set zu speichern, kostet bei einem einzelnen 20-Buchstaben-Wort 210 Buchstaben. Ein Trie speichert jedes gemeinsame Präfix nur einmal und beantwortet beide Fragen mit einem einzigen Durchlauf.
Sollte ein Trie-Knoten ein Array mit 26 Verweisen oder eine Hash-Map verwenden?
Ein Array findet ein Kind über einen Index, benötigt aber 26 Speicherplätze pro Knoten, selbst wenn der Knoten nur ein Kind hat. Eine Map speichert nur die vorhandenen Kinder und funktioniert für jedes Alphabet, benötigt dafür aber einen Hash pro Buchstabe. Für englische Kleinbuchstaben funktionieren beide; für Unicode oder dünn besetzte Tries spart eine Map Speicher.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def trieOps(ops, words):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
ops = ["insert", "search", "startsWith", "insert", "search"] words = ["card", "car", "car", "car", "car"]
Erwartete Ausgabe
["null", "false", "true", "null", "true"]