0Pricing
Competitive Programming Academy · Lektion

Tries für Präfixabfragen

Speichern und suchen Sie Wortpräfixe schnell

Tries für Präfixabfragen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 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 Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.

Wörter clever speichern

Ein Trie ist ein Baum, der Wörter speichert, indem er gemeinsame Präfixe teilt. Dadurch lassen sich Präfixabfragen blitzschnell beantworten. 🌳

Warum nicht einfach ein Set?

Ein Set beantwortet Abfragen nach vollständigen Wörtern, aber Tries unterstützen auch Präfixabfragen wie: Beginnt ein Wort mit pre?

Knoten und Kanten

Jeder Knoten entspricht einer Position in einem Wort, und jede Kante ist mit einem Zeichen auf dem Weg von der Wurzel beschriftet.

Kinder als Dict

In Python ist der einfachste Knoten ein Dict, das ein Zeichen seinem Kindknoten zuordnet. Klar und flexibel.

root = {}

Ein Wort einfügen

Zum Einfügen gehen Sie Zeichen für Zeichen durch das Wort und erstellen ein Kind, wenn noch keines vorhanden ist.

node = root
for c in word:
    node = node.setdefault(c, {})

Wortenden markieren

Setzen Sie nach dem Einfügen ein Ende-Flag, damit Sie ein vollständiges Wort von einem bloßen Präfix unterscheiden können.

node['#'] = True

Ein vollständiges Wort suchen

Zum Suchen folgen Sie den Zeichen. Fehlt ein Schritt, ist das Wort nicht vorhanden. Prüfen Sie anschließend das Ende-Flag.

for c in word:
    if c not in node:
        return False
    node = node[c]

Ein Präfix prüfen

Eine Präfixabfrage folgt demselben Weg, überspringt aber die Prüfung des Ende-Flags. Wenn Sie den letzten Knoten erreichen, lautet die Antwort Ja.

Laufzeitkomplexität

Einfügen und Suchen kosten O(L), wobei L die Wortlänge ist – unabhängig davon, wie viele Wörter Sie gespeichert haben. Entscheidend ist die Länge.

Wörter nach Präfix zählen

Speichern Sie an jedem Knoten einen Zähler, um sofort zu ermitteln, wie viele gespeicherte Wörter ein bestimmtes Präfix teilen.

Wo Tries helfen

Tries ermöglichen Autovervollständigung, Wörterbuchabfragen und Probleme zum maximalen XOR auf Bits. Ein grundlegendes Werkzeug für String-Aufgaben in Wettbewerben.

Kurzer Check

Überprüfen Sie, welchen Aufwand eine Trie-Suche tatsächlich hat.

Zusammenfassung: Tries abgeschlossen

Sie können jetzt einen Trie aufbauen, in O(L) einfügen und suchen sowie schnelle Präfix- und Zählabfragen beantworten. 🌟

Häufig gestellte Fragen

Ist die Lektion „Tries für Präfixabfragen“ kostenlos?

Ja — der vollständige Text von „Tries für Präfixabfragen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Tries für Präfixabfragen“?

Speichern und suchen Sie Wortpräfixe schnell Du übst Competitive Programming Academy 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 Competitive Programming Academy zu starten?

Keine Vorkenntnisse erforderlich. Competitive Programming Academy 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 4 von 4.

Wie lange dauert die Lektion „Tries für Präfixabfragen“?

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 Competitive Programming Academy-Lektion Code schreiben und ausführen?

Ja. Jede Competitive Programming Academy-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

  1. KMP-Präfixfunktion
  2. Polynomiales String-Hashing
  3. Z-Funktion für Mustersuche
  4. Tries für Präfixabfragen
← Zurück zu Competitive Programming Academy