Word Search II: Trie und Backtracking auf einem Gitter
Fügen Sie alle Zielwörter in einen Trie ein und führen Sie auf einem 2D-Brett DFS-Backtracking aus, um gleichzeitig alle gültigen Wörter in O(m × n × 4^L) zu finden.
Word Search II: Trie und Backtracking auf einem Gitter ist eine kostenlose DSA Interview Prep-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 DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Problem Word Search II
Word Search II (LeetCode 212): Gegeben sind ein m × n-Spielfeld aus Zeichen und eine Liste von Wörtern. Finden Sie alle Wörter, die aus aufeinanderfolgenden horizontal oder vertikal benachbarten Zellen gebildet werden können, wobei jede Zelle nur einmal verwendet werden darf. Dies ist schwieriger als Word Search I (ein einzelnes Wort), da wir alle passenden Wörter gleichzeitig finden müssen — Word Search I naiv für jedes Wort auszuführen, ergibt O(W × m × n × 4^L) und ist zu langsam.
Warum Trie + Backtracking?
Wenn Sie alle Zielwörter in einen Trie einfügen und anschließend auf dem Spielfeld DFS-Backtracking ausführen, können Sie alle Wörter gleichzeitig suchen. Statt an jeder Spielfeldzelle zu prüfen, „ob dieser Pfad mein Zielwort bildet“, prüfen Sie, „ob dieser Pfad einem Präfix im Trie entspricht“. Sobald ein Trie-Präfix nicht mehr passt, beschneiden Sie den gesamten DFS-Zweig — dadurch vermeiden Sie redundante Arbeit bei allen Wörtern, die dieses Präfix gemeinsam haben.
Den Trie aus einer Wortliste aufbauen
Fügen Sie alle Wörter in einen Trie ein. Speichern Sie das vollständige Wort im Blattknoten (in node.word) statt nur eines booleschen Werts. So können Sie das Wort beim Finden eines vollständigen Treffers während des Backtrackings sofort zu den Ergebnissen hinzufügen, ohne es Zeichen für Zeichen rekonstruieren zu müssen.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(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.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')DFS-Backtracking auf dem Spielfeld
Starten Sie eine DFS von jeder Zelle des Spielfelds. Gehen Sie bei jedem Schritt wie folgt vor: (1) Prüfen Sie, ob das Zeichen der aktuellen Zelle als Kind im aktuellen Trie-Knoten vorhanden ist. (2) Falls ja, markieren Sie die Zelle als besucht (setzen Sie sie auf einen Platzhalter wie '#') und rufen Sie die Rekursion für die 4 Nachbarn auf. (3) Stellen Sie die Zelle nach der Rekursion wieder her (heben Sie die Markierung auf). Wenn ein Trie-Knoten ein von None verschiedenes word enthält, fügen Sie es zu den Ergebnissen hinzu und setzen Sie es auf None, um Duplikate zu vermeiden.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, 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.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']Komplexitätsanalyse
Zeit: O(m × n × 4^L), wobei L die maximale Wortlänge ist. Für jede der m×n Startzellen erkundet die DFS bis zu 4^L Pfade. Der Trie beschneidet Pfade, die keinem Wortpräfix entsprechen, sodass die Suche in der Praxis deutlich schneller ist. Das Erstellen des Tries benötigt O(W × L), wobei W die Anzahl der Wörter ist. Speicher: O(W × L) für den Trie plus O(L) für die maximale Tiefe des Rekursionsstapels.
Beschneiden: Blattknoten nach dem Finden entfernen
Entfernen Sie nach dem Finden eines Wortes den Blattknoten aus dem Trie (setzen Sie nicht nur das Wort auf null), wenn er keine Kinder besitzt. Dadurch verhindern Sie, dass bei späteren DFS-Aufrufen tote Zweige erneut besucht werden. Wenn die Kinder eines Knotens nach dem Finden des Wortes leer sind, entfernen Sie den Knoten aus dem Children-Dictionary seines übergeordneten Knotens. Diese Optimierung ist besonders wirkungsvoll, wenn viele Wörter lange Präfixe gemeinsam haben.
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')Warum das Speichern von word im Knoten besser ist
Das Speichern des vollständigen Wortes im Blattknoten des Tries (statt es aus dem DFS-Pfad zu rekonstruieren) hat zwei Vorteile: (1) Das Wort kann beim Finden eines Treffers in O(1) abgerufen werden, statt den Pfad in O(L) rekonstruieren zu müssen. (2) node.word = None nach dem Finden des Wortes ermöglicht eine saubere Deduplizierung in O(1), ohne eine separate Ergebnismenge zu benötigen. Gerade bei Word Search II ist das Verhindern von Duplikaten wichtig, da dasselbe Wort theoretisch über verschiedene Pfade gefunden werden kann.
Besuchte Zellen direkt im Spielfeld markieren
Statt einer separaten Menge visited (die pro DFS-Pfad O(m × n) Speicher benötigen würde) markieren wir Zellen direkt im Spielfeld, indem wir ihr Zeichen durch einen Platzhalter wie '#' ersetzen. Nach der Rückkehr aus der DFS stellen wir das ursprüngliche Zeichen wieder her. Diese Technik (1) benötigt pro Zelle O(1) zusätzlichen Speicher, (2) verhindert automatisch das erneute Besuchen innerhalb eines einzelnen Pfades und (3) ist für die Trie-Traversierung vollständig transparent, da '#' niemals im Trie vorkommen wird.
Zu behandelnde Sonderfälle
Wichtige Sonderfälle: (1) doppelte Wörter in der Wortliste — speichern Sie sie in einer Menge oder verwenden Sie den Trick node.word = None, um Duplikate in den Ergebnissen zu verhindern; (2) sehr lange Wörter, die die Abmessungen des Spielfelds überschreiten — sie können nicht gebildet werden, aber die DFS behandelt dies automatisch, indem ihr die benachbarten Zellen ausgehen; (3) ein Spielfeld mit nur einer Zelle — es können nur Wörter aus einem einzelnen Zeichen gefunden werden; (4) dasselbe Wort kann über verschiedene Pfade gefunden werden — der Trick node.word = None verhindert eine doppelte Zählung.
Vergleich mit dem naiven Ansatz
Naiver Ansatz: Für jedes der W Wörter wird Word Search I ausgeführt: O(W × m × n × 4^L). Mit dem Trie werden alle Wörter gleichzeitig gesucht: O(m × n × 4^L), unabhängig von W. Bei W=1000 Wörtern der Länge 10 auf einem 10×10-Spielfeld ist der naive Ansatz 1000-mal langsamer als der Trie-Ansatz. Der Trie fungiert als gemeinsamer Präfixfilter, der die Kosten auf alle Wörter verteilt — ein klassisches Beispiel dafür, wie eine Datenstruktur eine asymptotische Verbesserung ermöglicht.
Zusammenfassung der vollständigen Lösung
Vollständige Lösung für Word Search II: Erstellen Sie einen Trie mit den Wörtern und speichern Sie die Wortzeichenfolge im Blatt. Führen Sie für jede Spielfeldzelle eine DFS aus: Prüfen Sie, ob das aktuelle Zeichen im aktuellen Trie-Knoten vorhanden ist, markieren Sie die Zelle mit '#', rufen Sie die Rekursion für die 4 Nachbarn auf und stellen Sie die Zelle wieder her. Wenn node.word nicht null ist, fügen Sie das Wort zu den Ergebnissen hinzu und setzen Sie node.word auf null. Optional können Sie leere Trie-Zweige nach ihrer Verwendung beschneiden. Geben Sie die Ergebnisliste zurück. Zeit: O(m×n×4^L), Speicher: O(W×L) für den Trie + O(L) Rekursion.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return resultSchnelltest
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: Word Search II verwendet einen Trie, um die gleichzeitige Suche nach mehreren Wörtern mit gemeinsamem Präfix-Beschneiden zu ermöglichen, das Speichern der Wortzeichenfolge im Trie-Blatt ermöglicht das Abrufen des Wortes in O(1) und eine einfache Deduplizierung, indem die Zeichenfolge nach dem Finden auf None gesetzt wird und die Markierung besuchter Zellen direkt im Spielfeld vermeidet O(m×n) zusätzlichen Speicher pro DFS-Pfad. Damit ist der Kurs Tries and String Algorithms abgeschlossen — Sie beherrschen nun eine der leistungsfähigsten stringspezifischen Datenstrukturen, die in Interviews verwendet werden.
Häufig gestellte Fragen
Ist die Lektion „Word Search II: Trie und Backtracking auf einem Gitter“ kostenlos?
Ja — der vollständige Text von „Word Search II: Trie und Backtracking auf einem Gitter“ 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 „Word Search II: Trie und Backtracking auf einem Gitter“?
Fügen Sie alle Zielwörter in einen Trie ein und führen Sie auf einem 2D-Brett DFS-Backtracking aus, um gleichzeitig alle gültigen Wörter in O(m × n × 4^L) zu finden. 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 4 von 4.
Wie lange dauert die Lektion „Word Search II: Trie und Backtracking auf einem Gitter“?
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