Word Search II: Trie og tilbakesporing i rutenett
Sett inn alle målordene i et trie, og kjør DFS med tilbakesporing på et 2D-brett for å finne alle gyldige ord samtidig i O(m × n × 4^L).
Word Search II: Trie og tilbakesporing i rutenett er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Problemet med Word Search II
Word Search II (LeetCode 212): Gitt et m × n-brett med tegn og en liste med ord skal vi finne alle ord som kan dannes av sekvensielt tilstøtende celler (vannrett eller loddrett), der hver celle bare kan brukes én gang. Dette er vanskeligere enn Word Search I (ett enkelt ord), fordi vi må finne alle samsvarende ord samtidig — det blir for tregt å kjøre Word Search I naivt for hvert ord, med kompleksiteten O(W × m × n × 4^L).
Hvorfor trie + backtracking?
Ved å sette inn alle målordene i en trie og deretter kjøre DFS-backtracking på brettet kan vi søke etter alle ordene samtidig. Ved hver brettcelle kontrollerer vi i stedet for «staver denne banen målordet mitt?» om «denne banen samsvarer med et prefiks i trien?». Så snart et trie-prefiks ikke samsvarer, beskjærer vi hele DFS-grenen — og unngår overflødig arbeid på tvers av alle ord som deler prefiks.
Bygge en trie fra en ordliste
Sett inn alle ordene i en trie. Lagre hele ordet i bladnoden (i node.word) i stedet for bare en boolsk verdi. Da kan vi umiddelbart legge ordet til i resultatene når vi finner et komplett treff under backtracking, uten å måtte bygge det opp tegn for tegn.
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 på rutenettet
Start en DFS fra hver celle på brettet. Ved hvert trinn: (1) kontroller om tegnet i den gjeldende cellen finnes som et barn i den gjeldende trie-noden; (2) hvis ja, markerer De cellen som besøkt (sett den til en sentinelverdi som '#') og kaller funksjonen rekursivt for de 4 naboene; (3) etter rekursjonen gjenoppretter De cellen (fjerner markeringen). Når en trie-node har et ikke-None word, legger De det til i resultatene og setter det til None for å unngå duplikater.
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']Kompleksitetsanalyse
Tid: O(m × n × 4^L), der L er den maksimale ordlengden. For hver av de m×n startcellene utforsker DFS opptil 4^L stier. Trien beskjærer stier som ikke samsvarer med noe ordprefiks, så søket går i praksis mye raskere. Det tar O(W × L) å bygge trien, der W er antallet ord. Plass: O(W × L) for trien, pluss O(L) for dybden på rekursjonsstakken.
Beskjæring: fjerne bladnoder etter treff
Etter at et ord er funnet, bør vi fjerne bladnoden fra trien (ikke bare sette ordet til null) hvis den ikke har barn. Dette hindrer at døde grener besøkes på nytt i senere DFS-kall. Når en nodes barn blir tomme etter at ordet er funnet, fjerner vi noden fra forelderens ordbok over barn. Denne optimaliseringen er betydelig når mange ord deler lange prefikser.
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')Hvorfor det er bedre å lagre word i noden
Å lagre hele ordet i trie-bladnoden i stedet for å bygge det opp fra DFS-stien har to fordeler: (1) O(1)-henting av ordet når et treff finnes, i stedet for O(L) for å bygge opp stien; (2) å sette node.word = None etter at ordet er funnet gir en ryddig deduplisering på O(1), uten behov for et separat resultatsett. For Word Search II er det spesielt viktig å hindre duplikater, fordi det samme ordet i teorien kan bli funnet via ulike stier.
In-place-merking av besøkte celler
I stedet for et separat visited-sett, som ville krevd O(m × n) plass per DFS-sti, markerer vi cellene på stedet ved å erstatte tegnet med en sentinelverdi som '#'. Etter at DFS returnerer, gjenoppretter vi det opprinnelige tegnet. Denne teknikken: (1) bruker O(1) ekstra plass per celle; (2) hindrer automatisk at en celle besøkes på nytt i samme sti; (3) påvirker ikke trie-gjennomgangen, siden '#' aldri vil finnes i trien.
Spesialtilfeller som må håndteres
Viktige spesialtilfeller: (1) duplikatord i ordlisten — lagre ordene i et sett, eller bruk node.word = None-metoden for å hindre duplikater i resultatene; (2) svært lange ord som overskrider brettets dimensjoner — de kan ikke dannes, men DFS håndterer dette naturlig ved å gå tom for tilstøtende celler; (3) brett med én celle — bare ord med ett tegn kan finnes; (4) det samme ordet kan finnes via ulike stier — node.word = None-metoden hindrer dobbel opptelling.
Sammenligning med den naive metoden
Naiv metode: Kjør Word Search I for hvert av W ord, med kompleksiteten O(W × m × n × 4^L). Med trien søkes alle ordene samtidig: O(m × n × 4^L), uavhengig av W. For W=1000 ord med lengde 10 på et brett på 10×10 celler er den naive metoden 1000× tregere enn trie-metoden. Trien fungerer som et delt prefiksfilter som fordeler kostnaden på alle ordene — et klassisk eksempel på å bruke en datastruktur for å oppnå asymptotisk forbedring.
Fullstendig løsningsoppsummering
Fullstendig løsning for Word Search II: Bygg en trie med ordene, og lagre ordstrengen i bladnoden. Kjør DFS fra hver brettcelle: kontroller om det gjeldende tegnet finnes i den gjeldende trie-noden, marker cellen med '#', kall funksjonen rekursivt for de 4 naboene, og gjenopprett cellen. Når node.word ikke er None, legger vi ordet til i resultatene og setter det til None. Beskjær eventuelt tomme trie-grener etter bruk. Returner resultatlisten. Tid: O(m×n×4^L), plass: O(W×L) for trien + O(L) rekursjon.
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 resultHurtigsjekk
Test forståelsen Deres av konseptene innen Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen har De lært: Word Search II bruker en trie for samtidig søking etter flere ord med delt prefiksbeskjæring, lagring av ordstrengen i trie-bladet muliggjør O(1)-henting av ordet og enkel deduplisering ved å sette den til None etter at ordet er funnet, og in-place-merking av besøkte celler med '#' unngår O(m×n) ekstra plass per DFS-sti. Dette fullfører kurset Tries and String Algorithms — De har nå fått kontroll på en av de mest kraftfulle strengspesifikke datastrukturene som brukes i intervjuer.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Word Search II: Trie og tilbakesporing i rutenett» gratis?
Ja – hele teksten i «Word Search II: Trie og tilbakesporing i rutenett» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Word Search II: Trie og tilbakesporing i rutenett»?
Sett inn alle målordene i et trie, og kjør DFS med tilbakesporing på et 2D-brett for å finne alle gyldige ord samtidig i O(m × n × 4^L). Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Word Search II: Trie og tilbakesporing i rutenett»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- TrieNode-klassen: Sett inn og søk
- Prefikssøk og Starts-With
- Søk med jokertegn og regulære uttrykk i et trie
- Word Search II: Trie og tilbakesporing i rutenett