Wildcard- und Regex-Suche in einem Trie

Die Standardsuche in einem Trie verarbeitet exakte Zeichen. Die Wildcard-Suche fügt ein Sonderzeichen '.' hinzu, das jedem einzelnen Zeichen entspricht. Wenn bei der Suche ein '.' angetroffen wird, dürfen wir nicht nur einem bestimmten Kind folgen, sondern müssen alle Kinder ausprobieren — eine Verzweigung. Das ist die zentrale Idee hinter LeetCode 211 „Design Add and Search Words Data Structure“. Jedes '.' vervielfacht die Suchpfade um die Anzahl der Kinder auf dieser Ebene.

Implementieren Sie die Wildcard-Suche mit einer rekursiven DFS-Hilfsfunktion. Für jedes Zeichen im Muster gilt: Handelt es sich um ein Literalzeichen, folgen Sie dem entsprechenden Kind (oder geben Sie False zurück, wenn es fehlt); handelt es sich um '.', rufen Sie die Funktion für alle Kinder rekursiv auf und geben Sie True zurück, sobald einer der Aufrufe erfolgreich ist. Geben Sie am Ende des Musters node.is_end zurück.

Wenn ein '.' angetroffen wird, rufen wir any(dfs(child, i+1) for child in node.children.values()) auf. Der Generator von any() verwendet eine Kurzschlussauswertung — er beendet die Suche, sobald ein Kind True zurückgibt. Dadurch vermeiden wir unnötige Erkundungen. Im schlimmsten Fall (ein Muster, das vollständig aus '.' besteht) werden alle Pfade erkundet — die Komplexität beträgt O(26^k), wobei k die Anzahl der Punkte ist. Dadurch sind Muster wie '....' bei großen Tries teuer.

Ein iterativer Ansatz verwendet eine Warteschlange mit Paaren aus (node, index). Beginnen Sie mit (root, 0). Geben Sie True zurück, wenn für ein Paar index == len(word) und node.is_end gilt. Verarbeiten Sie andernfalls das aktuelle Zeichen: Bei '.' fügen Sie alle Kinder zur Warteschlange hinzu, bei einem Literalzeichen nur das passende Kind. Im Wesentlichen handelt es sich dabei um eine BFS über die Pfade des Tries.

Bei einem Muster ohne Wildcards beträgt die Laufzeit O(m). Bei einem Muster mit k Wildcards liegt der Worst Case bei O(26^k × m) — die Laufzeit wächst exponentiell mit der Anzahl der Wildcards. In der Praxis sind Wildcards normalerweise selten und der Trie ist flach, sodass die Leistung akzeptabel ist. Bei Mustern, die ausschließlich aus Wildcards bestehen (z. B. beim Abgleich aller Wörter der Länge k), degeneriert die Suche zu einer vollständigen Traversierung des Tries.

Eine Erweiterung auf vollständige reguläre Ausdrücke (z. B. '*' für null oder mehr Zeichen) erfordert eine andere Verarbeitung. Ein '*' kann jedes Suffix abgleichen. Daher müssen wir beim Auftreten dieses Zeichens alle Trie-Pfade ab dem aktuellen Knoten ausprobieren. Eine echte Regex-Suche in einem Trie ist komplex — sie bleibt normalerweise der Konstruktion von NFA/DFA vorbehalten. In Interviews sind einstellige Wildcards ('.') das Standardmuster.

Glob-Abgleich mit '?' (beliebiges einzelnes Zeichen) und '*' (beliebige Sequenz einschließlich einer leeren Sequenz) lässt sich mit DP implementieren. Bei einer Implementierung in einem Trie entspricht '?' einer Verzweigung auf einer Ebene (wie '.') und '*' einer mehrstufigen DFS. Der kombinierte DP-Ansatz: dp[i][j] = True, wenn pattern[0..i] zu string[0..j] passt. Die interviewende Person gibt normalerweise vor, welche Variante implementiert werden soll.

Wildcards in Tries werden in IP-Routingtabellen verwendet, wobei '*' als Präfix-Wildcard fungiert. Ein Router speichert Routenpräfixe wie '192.168.*' und gleicht eingehende Adressen damit ab. Das Longest-Prefix-Matching (die spezifischste Route gewinnt) wird implementiert, indem der Trie so tief wie möglich durchlaufen und der zuletzt gefundene Treffer verwendet wird. Dies ist eine praktische Anwendung von Präfix- und Wildcard-Operationen auf Tries.

Wenn ein Trie-Knoten keine Kinder besitzt (also ein Blatt ist) und is_end = False gilt, liefert jede Suche, die ihn erreicht, False. Bei der Wildcard-Suche können Sie diese Sackgassenknoten vor dem rekursiven Aufruf überspringen und so unnötige Aufrufe vermeiden. Wenn jeder Knoten eine word_count-Angabe (die Gesamtzahl der Wörter im Teilbaum) enthält, lässt sich ein vollständiger Teilbaum überspringen, wenn kein Wort die Längenbedingungen des verbleibenden Musters erfüllen kann.

Eine übersichtliche, interviewtaugliche WordDictionary-Klasse, die Einfügen und die Suche mit Punkt-Wildcards in einer Klasse kombiniert. Dies ist genau die Implementierung, die für LeetCode 211 erwartet wird. Die rekursive Suche mit dem kurzschlussfähigen any() ist kompakt und zeigt die Verzweigungslogik für Interviewerinnen und Interviewer klar.

dict.setdefault(key, default) gibt den Wert für key zurück, falls dieser vorhanden ist, fügt andernfalls default ein und gibt ihn zurück. Die Verwendung von node.setdefault(c, {}) beim Einfügen macht die If-Else-Prüfung überflüssig: Das untergeordnete Dictionary wird bei Bedarf erstellt und in jedem Fall zurückgegeben. Dadurch wird das Einfügen zu einer einzeiligen Traversierung: for c in word: node = node.setdefault(c, {}). Sauber und Pythonic.

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.

In dieser Lektion haben Sie gelernt: Die Wildcard '.' erfordert an der passenden Position eine Verzweigung auf alle Kinder mithilfe einer rekursiven DFS, die Verwendung von any() mit einem Generator ermöglicht eine Kurzschlussauswertung für den vorzeitigen Abbruch und setdefault ermöglicht das kompakte Einfügen in einen Trie mit einer einzigen Zeile. Als Nächstes kombinieren wir Trie und Backtracking, um Word Search II zu lösen — mehrere Wörter gleichzeitig auf einem 2D-Spielfeld zu finden.