Wildcard- og regex-søgning i et trie
Understøt matchning med wildcardet '.' ved at forgrene søgningen til alle børn på det pågældende niveau, og løs problemet design-add-and-search-words-data-structure.
Wildcard- og regex-søgning i et trie er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Problemet med søgning med jokertegn
Standardtrie-søgning håndterer nøjagtige tegn. Søgning med jokertegn tilføjer et specialtegn '.', der matcher ét vilkårligt tegn. Når vi møder et '.' under søgningen, skal vi i stedet for at følge ét bestemt barn afprøve alle børn — en forgrening. Dette er kerneideen bag LeetCode 211 'Design Add and Search Words Data Structure'. Hvert '.' ganger antallet af søgestier med antallet af børn på det pågældende niveau.
Rekursiv søgning med jokertegn
Implementer søgning med jokertegn ved hjælp af en rekursiv DFS-hjælpefunktion. For hvert tegn i mønstret: Hvis det er et bogstaveligt tegn, følg det specifikke barn (eller returner False, hvis det mangler); hvis det er '.', kald funktionen rekursivt på alle børn, og returner True, hvis et af dem lykkes. Når mønstret slutter, returner node.is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(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 search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end
c = word[i]
if c == '.':
return any(dfs(child, i+1) for child in node.children.values())
if c not in node.children:
return False
return dfs(node.children[c], i+1)
return dfs(self.root, 0)
wd = WordDictionary()
wd.addWord('bad')
wd.addWord('dad')
wd.addWord('mad')
print(wd.search('.ad')) # True
print(wd.search('b..')) # True
print(wd.search('pad')) # FalseHvorfor bruge any() til forgrening
Når vi møder et '.', kalder vi any(dfs(child, i+1) for child in node.children.values()). Generatoren any() anvender kortslutning — den stopper, så snart ét barn returnerer True. Det undgår unødvendig udforskning. I værste fald, når mønstret kun består af '.', udforsker vi alle stier — kompleksiteten er O(26^k), hvor k er antallet af punktummer, hvilket gør mønstre som '....' dyre i store tries.
Iterativ søgning med jokertegn ved hjælp af køer
En iterativ tilgang bruger en kø med par af typen (node, index). Start med (root, 0). For hvert par skal du returnere True, hvis index == len(word) og node.is_end. Ellers behandles det aktuelle tegn: ved '.' sættes alle børn i køen; ved et bogstaveligt tegn sættes kun det matchende barn i køen. Dette er i praksis BFS over stier i trien.
from collections import deque
def search_iterative(root, word):
queue = deque([(root, 0)])
while queue:
node, i = queue.popleft()
if i == len(word):
if node.is_end:
return True
continue
c = word[i]
if c == '.':
for child in node.children.values():
queue.append((child, i+1))
elif c in node.children:
queue.append((node.children[c], i+1))
return False
print('Iterative BFS-based wildcard search')Kompleksitetsanalyse af søgning med jokertegn
For et mønster uden jokertegn er søgningen O(m). For et mønster med k jokertegn er værste fald O(26^k × m) — eksponentielt i antallet af jokertegn. I praksis er jokertegnene normalt spredt, og trien er lav, så ydeevnen er acceptabel. For mønstre, der udelukkende består af jokertegn (for eksempel matchning af alle ord med længden k), udarter søgningen til et komplet gennemløb af trien.
Regulære udtryk ud over jokertegn for enkelttegn
En udvidelse til fulde regulære udtryk (for eksempel '*', der matcher nul eller flere tegn) kræver en anden håndtering. Et '*' kan matche et vilkårligt suffiks, så når vi møder det, skal vi afprøve alle trie-stier fra den aktuelle node. Ægte matchning med regulære udtryk i en trie er kompleks — den er normalt forbeholdt NFA/DFA-konstruktioner. I interviews er jokertegn for enkelttegn ('.') det almindelige mønster.
Matchning af glob-mønstre
Matchning af glob-mønstre med '?' (et vilkårligt enkelt tegn) og '*' (en vilkårlig sekvens, også en tom) kan implementeres med DP. Hvis det implementeres i en trie, svarer '?' til forgrening på ét niveau (ligesom '.'), og '*' svarer til DFS over flere niveauer. Den kombinerede DP-tilgang: dp[i][j] = True, hvis pattern[0..i] matcher string[0..j]. Intervieweren angiver normalt, hvilken variant der skal implementeres.
Praktisk anvendelse: routing af IP-adresser
Tries med jokertegn bruges i IP-routingtabeller, hvor '*' fungerer som jokertegn for et præfiks. En router gemmer rutepræfikser som '192.168.*' og matcher indkommende adresser. Matchning af længste præfiks (den mest specifikke rute vinder) implementeres ved at gennemløbe trien så dybt som muligt og bruge det senest registrerede match. Dette er en anvendelse fra den virkelige verden af tries' præfiks- og jokertegnsoperationer.
Optimering: beskæring af døde grene
Når en trienode ikke har nogen børn (et blad), og is_end = False, returnerer enhver søgning, der når den, False. Under søgning med jokertegn kan vi springe disse blindgydenoder over, før vi kalder funktionen rekursivt, og dermed beskære unødvendige kald. Hvis hver node vedligeholder en word_count (det samlede antal ord i undertræet), kan vi springe et helt undertræ over, hvis ingen ord opfylder begrænsningerne for den resterende møsterlængde.
Komplet WordDictionary-klasse (klar til interview)
En ren, interviewklar WordDictionary, der kombinerer insert og søgning med punktum som jokertegn i én klasse. Dette er den præcise implementering, der forventes til LeetCode 211. Den rekursive søgning med kortsluttende any() er kortfattet og viser tydeligt forgreningslogikken for interviewere.
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for c in word:
node = node.setdefault(c, {})
node['#'] = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return '#' in node
if word[i] == '.':
return any(dfs(v, i+1) for k, v in node.items() if k != '#')
nxt = node.get(word[i])
return dfs(nxt, i+1) if nxt is not None else False
return dfs(self.root, 0)
wd = WordDictionary()
for w in ['at','and','an','add']:
wd.addWord(w)
print(wd.search('a.')) # True (at, an)
print(wd.search('.nd')) # True (and)
print(wd.search('...')) # True (and, add)
print(wd.search('x.')) # FalseBrug af setdefault til en kompakt trie
dict.setdefault(key, default) returnerer værdien for key, hvis den findes; ellers indsætter den default og returnerer den. Ved at bruge node.setdefault(c, {}) i insert undgår du kontrollen med if-else: Den opretter ordbogen for barnet, hvis den mangler, og returnerer den under alle omstændigheder. Det gør insert til et gennemløb på én linje: for c in word: node = node.setdefault(c, {}). Rent og Python-idiomatisk.
Hurtigt tjek
Test din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.
Opsummering af lektionen
I denne lektion lærte du: jokertegnet '.' kræver forgrening til alle børn på den matchende position ved hjælp af rekursiv DFS, brug af any() med en generator giver kortsluttende evaluering, så søgningen kan afsluttes tidligt, og setdefault muliggør en kompakt trie-insert på én linje. Dernæst kombinerer vi trie og backtracking for at løse Word Search II — finde flere ord samtidigt på et todimensionelt bræt.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Wildcard- og regex-søgning i et trie” gratis?
Ja — hele teksten til “Wildcard- og regex-søgning i et trie” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Wildcard- og regex-søgning i et trie”?
Understøt matchning med wildcardet '.' ved at forgrene søgningen til alle børn på det pågældende niveau, og løs problemet design-add-and-search-words-data-structure. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Wildcard- og regex-søgning i et trie”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- TrieNode-klassen: Indsættelse og søgning
- Præfikssøgning og Starts-With
- Wildcard- og regex-søgning i et trie
- Word Search II: Trie + backtracking på et gitter