Präfixsuche und Starts-With
Fügen Sie eine starts_with-Methode hinzu, die true zurückgibt, wenn ein eingefügtes Wort ein vorgegebenes Präfix teilt, und verwenden Sie sie zur Implementierung von Autocomplete-Vorschlägen.
Präfixsuche und Starts-With ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Die Stärke von Präfixabfragen
Der entscheidende Vorteil eines Tries gegenüber einer Hash-Map sind effiziente Präfixabfragen. Eine Präfixabfrage beantwortet Fragen wie: „Wie viele gespeicherte Wörter beginnen mit diesem Präfix?“, „Welche gespeicherten Wörter beginnen mit diesem Präfix?“ oder einfach „Existiert ein Wort mit diesem Präfix?“. Diese Abfragen benötigen O(p), wobei p die Präfixlänge ist, unabhängig von der Gesamtzahl der gespeicherten Wörter — dadurch sind Tries ideal für Autovervollständigung und Suchvorschläge.
Die Methode starts_with
starts_with(prefix) gibt True zurück, wenn ein gespeichertes Wort mit dem angegebenen Präfix beginnt. Durchlaufen Sie den Trie und folgen Sie jedem Zeichen des Präfixes. Wenn allen Zeichen gefolgt werden kann, ohne dass eine Kante fehlt, ist das Präfix vorhanden und mindestens ein Wort beginnt damit. Die Implementierung ist mit der von search identisch, außer dass wir unmittelbar nach dem vollständigen Durchlauf True zurückgeben — is_end wird nicht geprüft.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # FalseAutovervollständigung: Alle Wörter mit einem Präfix finden
Um Autovervollständigung zu implementieren, durchlaufen Sie den Trie bis zum Endknoten des Präfixes und führen anschließend von diesem Knoten aus eine DFS (oder BFS) durch, um alle von dort ausgehenden Wörter zu sammeln. Stellen Sie jedem gesammelten Suffix das Präfix voran, um die vollständigen Wörter zu rekonstruieren. Dies ist eine Operation mit O(p + W), wobei W die Gesamtzahl der Zeichen in allen passenden Wörtern ist.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return []
node = node.children[c]
# DFS from prefix end node
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for char, child in n.children.items():
dfs(child, path + char)
dfs(node, '')
return results
t = Trie()
for w in ['apple','app','application','apply','apt']:
t.insert(w)
print(t.autocomplete('app')) # ['app','apple','apply','application']Sortierte Vorschläge zurückgeben
Für sortierte Autovervollständigung durchlaufen Sie die Kinder während der DFS in alphabetischer Reihenfolge (indem Sie über sorted(node.children.items()) iterieren). Da children in einem Dict gespeichert wird, verursacht dies einen Overhead von O(ALPHABET_SIZE × depth), garantiert aber lexikografisch geordnete Ergebnisse. Ein Array-basierter Trie durchläuft die Kinder immer in alphabetischer Reihenfolge, da die Indizes 0-25 geordnet sind.
def dfs_sorted(node, prefix, results):
if node.is_end:
results.append(prefix)
for char in sorted(node.children.keys()): # alphabetical order
dfs_sorted(node.children[char], prefix + char, results)
print('Iterating children in sorted order gives lex-sorted suggestions')Top-K-Vorschläge für die Autovervollständigung
Für Top-K-Vorschläge nach Häufigkeit erweitern Sie jeden Knoten um eine Anzahl, wie oft das an dieser Stelle endende Wort gesucht wurde. Verwenden Sie beim Sammeln der Vorschläge einen Max-Heap der Größe k. Dadurch wird die O(W)-Ergebnismenge der DFS auf O(k) reduziert, ohne alle Treffer zu materialisieren. Suchmaschinen aus der Praxis kombinieren die Präfixsuche im Trie mit Häufigkeitsdaten, um schnell relevante Vorschläge zu liefern.
Den Trie für LeetCode 208 implementieren
LeetCode 208 'Implement Trie (Prefix Tree)' verlangt genau Folgendes: insert(word), search(word) mit einem Boolean für exakte Übereinstimmung und startsWith(prefix) mit einem Boolean für Präfixübereinstimmung. Dies ist die kanonische Trie-Implementierung. Denken Sie daran: search erfordert is_end=True; startsWith erfordert nur, dass der Präfixpfad existiert.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = True # '#' marks word end
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return '#' in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return True
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False
print(t.startsWith('app')) # True„#“ als Endmarker verwenden (Dict-Trie)
Eine elegante Abkürzung speichert den Trie als verschachtelte Dicts mit einem speziellen Sentinel-Schlüssel wie '#', der das Wortende markiert. Dadurch wird keine TrieNode-Klasse benötigt. Diese Variante ist kompakt und für Vorstellungsgespräche geeignet, aber etwas weniger übersichtlich als explizite TrieNode-Objekte. Beide Implementierungen sind akzeptabel; die Dict-Variante lässt sich unter Zeitdruck schneller schreiben.
Längsten gemeinsamen Präfix mit einem Trie finden
Um den längsten gemeinsamen Präfix einer Liste von Zeichenketten zu finden, fügen Sie alle Zeichenketten in den Trie ein und durchlaufen anschließend von der Wurzel aus den einzigen vorhandenen Pfad, solange folgende Bedingungen gelten: (1) Der aktuelle Knoten hat genau ein Kind und (2) is_end ist False. Stoppen Sie, sobald eine der Bedingungen nicht mehr gilt. Der durchlaufene Pfad ist der längste gemeinsame Präfix.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def longest_common_prefix(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
prefix = []
node = root
while len(node.children) == 1 and not node.is_end:
char, node = next(iter(node.children.items()))
prefix.append(char)
return ''.join(prefix)
print(longest_common_prefix(['flower','flow','flight'])) # 'fl'
print(longest_common_prefix(['dog','racecar','car'])) # ''Replace-Words-Problem
Replace Words (LeetCode 648): Ersetzen Sie bei einem Wörterbuch mit Wortstämmen und einem Satz jedes Wort im Satz durch den kürzesten passenden Stamm aus dem Wörterbuch. Fügen Sie alle Stämme in einen Trie ein. Durchlaufen Sie für jedes Wort im Satz den Trie, bis ein Stammende gefunden wird, und geben Sie diesen Stamm als Ersatz zurück. Wenn kein Stamm übereinstimmt, behalten Sie das ursprüngliche Wort bei. Dies läuft in O(total chars) statt in O(n × m) bei einer Brute-Force-Lösung.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def replaceWords(dictionary, sentence):
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def find_root(word):
node = root
for i, c in enumerate(word):
if c not in node.children: break
node = node.children[c]
if node.is_end:
return word[:i+1]
return word
return ' '.join(find_root(w) for w in sentence.split())
print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))Map-Sum-Pairs-Problem
Map Sum (LeetCode 677): Fügen Sie Schlüssel-Wert-Paare ein und geben Sie die Summe aller Werte zurück, deren Schlüssel mit einem bestimmten Präfix beginnen. Erweitern Sie jeden TrieNode um ein val-Feld. Durchlaufen Sie beim Einfügen den Trie bis zum Ende und setzen Sie den Wert; bei Summenabfragen durchlaufen Sie den Trie bis zum Endknoten des Präfixes und summieren per DFS alle darunterliegenden val-Felder. Alternativ können Sie während des Einfügens in jedem Knoten die kumulative Summe speichern, um Abfragen in O(p) zu ermöglichen.
Autocomplete mit begrenzter Ergebnisanzahl implementieren
In produktiven Autocomplete-Systemen ist es unpraktisch, alle Wörter mit einem Präfix zurückzugeben, wenn Tausende von Wörtern übereinstimmen. Verwenden Sie stattdessen während der DFS-Traversierung einen Max-Heap der Größe k: Halten Sie die bisher gefundenen k Wörter mit der höchsten Bewertung vor. Beenden Sie DFS-Zweige vorzeitig, wenn sie unmöglich ein Wort aus den Top-k enthalten können (Beschneiden anhand einer oberen Schranke für die Bewertung). Dadurch ergibt sich pro Abfrage für k Vorschläge eine Laufzeit von O(p + k × log k) — deutlich besser, als alle Treffer zu sammeln.
Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: starts_with durchläuft den Präfixpfad und gibt True zurück, wenn dieser existiert — eine Prüfung von is_end ist nicht erforderlich, autocomplete DFS sammelt alle Wörter ab dem Endknoten des Präfixes, indem beim Abstieg Zeichen angehängt werden und das Ergänzen von Knoten um Zähler oder Werte Summenabfragen und Top-k-Vorschläge ermöglicht. Als Nächstes erweitern wir den Trie um Wildcard- und Regex-Suche.
Häufig gestellte Fragen
Ist die Lektion „Präfixsuche und Starts-With“ kostenlos?
Ja — der vollständige Text von „Präfixsuche und Starts-With“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Präfixsuche und Starts-With“?
Fügen Sie eine starts_with-Methode hinzu, die true zurückgibt, wenn ein eingefügtes Wort ein vorgegebenes Präfix teilt, und verwenden Sie sie zur Implementierung von Autocomplete-Vorschlägen. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Präfixsuche und Starts-With“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- TrieNode-Klasse: Einfügen und Suchen
- Präfixsuche und Starts-With
- Wildcard- und Regex-Suche in einem Trie
- Word Search II: Trie und Backtracking auf einem Gitter