Wyszukiwanie z symbolami wieloznacznymi i wyrażeniami regularnymi w Trie
Obsługiwać dopasowanie symbolu wieloznacznego '.' przez przejście do wszystkich dzieci na danym poziomie i rozwiązywać problem design-add-and-search-words-data-structure
Wyszukiwanie z symbolami wieloznacznymi i wyrażeniami regularnymi w Trie to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem wyszukiwania z symbolami wieloznacznymi
Standardowe wyszukiwanie w trie obsługuje dokładne znaki. Wyszukiwanie z symbolem wieloznacznym dodaje specjalny znak '.', który dopasowuje dowolny pojedynczy znak. Po napotkaniu '.' podczas wyszukiwania zamiast przechodzić do jednego konkretnego dziecka musimy sprawdzić wszystkie dzieci — następuje rozgałęzienie. To podstawowa idea zadania LeetCode 211 „Design Add and Search Words Data Structure”. Każdy znak '.' zwielokrotnia liczbę ścieżek wyszukiwania przez liczbę dzieci na danym poziomie.
Rekurencyjne wyszukiwanie z symbolem wieloznacznym
Wyszukiwanie z symbolem wieloznacznym należy zaimplementować za pomocą rekurencyjnej funkcji pomocniczej DFS. Dla każdego znaku wzorca: jeśli jest to znak dosłowny, należy przejść do konkretnego dziecka (lub zwrócić False, jeśli go brakuje); jeśli jest to '.', należy wywołać rekurencję dla wszystkich dzieci i zwrócić True, jeśli którakolwiek ścieżka zakończy się powodzeniem. Po dojściu do końca wzorca należy zwrócić 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')) # FalseDlaczego używać any() przy rozgałęzieniu
Po napotkaniu '.' wywołujemy any(dfs(child, i+1) for child in node.children.values()). Generator any() stosuje wykonanie z krótkim spięciem — zatrzymuje się natychmiast, gdy jedno z dzieci zwróci True. Pozwala to uniknąć niepotrzebnego przeszukiwania. W najgorszym przypadku (wzorzec zawierający wyłącznie '.') przechodzimy wszystkimi ścieżkami — złożoność wynosi O(26^k), gdzie k to liczba kropek, dlatego wzorce takie jak '....' mogą być kosztowne dla dużych struktur trie.
Iteracyjne wyszukiwanie z symbolami wieloznacznymi i kolejkami
Podejście iteracyjne wykorzystuje kolejkę par (node, index). Rozpoczynamy od (root, 0). Dla każdej pary, jeśli index == len(word) i node.is_end, zwracamy True. W przeciwnym razie przetwarzamy bieżący znak: dla '.' dodajemy do kolejki wszystkie dzieci, a dla znaku dosłownego — tylko pasujące dziecko. Jest to w istocie BFS po ścieżkach w trie.
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')Analiza złożoności wyszukiwania z symbolem wieloznacznym
Dla wzorca bez symboli wieloznacznych wyszukiwanie ma złożoność O(m). Dla wzorca zawierającego k symboli wieloznacznych złożoność w najgorszym przypadku wynosi O(26^k × m) — jest wykładnicza względem liczby symboli wieloznacznych. W praktyce symbole wieloznaczne zwykle występują rzadko, a trie jest płytkie, więc wydajność pozostaje akceptowalna. W przypadku wzorców składających się wyłącznie z symboli wieloznacznych (np. dopasowujących wszystkie słowa o długości k) wyszukiwanie sprowadza się do pełnego przejścia po trie.
Wyszukiwanie za pomocą wyrażeń regularnych wykraczających poza symbole jednego znaku
Rozszerzenie rozwiązania do pełnych wyrażeń regularnych (np. '*' dopasowującego zero lub więcej znaków) wymaga innego podejścia. '*' może dopasować dowolny przyrostek, więc po jego napotkaniu musimy wypróbować wszystkie ścieżki trie od bieżącego węzła. Prawdziwe dopasowywanie wyrażeń regularnych w trie jest złożone — zwykle wykorzystuje się do tego konstrukcje NFA/DFA. Na rozmowach technicznych standardem są symbole wieloznaczne dopasowujące pojedynczy znak ('.').
Dopasowywanie wzorców glob
Dopasowywanie wzorców glob za pomocą '?' (dowolny pojedynczy znak) i '*' (dowolny ciąg, również pusty) można zaimplementować programowaniem dynamicznym. Jeśli rozwiązanie jest implementowane w trie, '?' odpowiada rozgałęzieniu na jednym poziomie (podobnie jak '.'), a '*' odpowiada wielopoziomowemu DFS. W podejściu łączącym te techniki: dp[i][j] = True, jeśli pattern[0..i] dopasowuje string[0..j]. Osoba przeprowadzająca rozmowę techniczną zwykle określa, który wariant należy zaimplementować.
Praktyczne zastosowanie: routing adresów IP
Trie z obsługą symboli wieloznacznych stosuje się w tablicach routingu IP, gdzie '*' pełni funkcję symbolu wieloznacznego prefiksu. Router przechowuje prefiksy tras, takie jak '192.168.*', i dopasowuje do nich przychodzące adresy. Dopasowywanie najdłuższego prefiksu (wygrywa najbardziej szczegółowa trasa) implementuje się przez przejście w trie tak głębokie, jak to możliwe, oraz wykorzystanie ostatniego napotkanego dopasowania. Jest to rzeczywiste zastosowanie operacji prefiksowych i operacji z symbolami wieloznacznymi w trie.
Optymalizacja: przycinanie martwych gałęzi
Gdy węzeł trie nie ma dzieci (jest liściem), a is_end = False, każde wyszukiwanie, które do niego dotrze, zwróci False. Podczas wyszukiwania z symbolem wieloznacznym można pomijać takie ślepe zaułki przed wywołaniem rekurencji, aby ograniczyć liczbę niepotrzebnych wywołań. Przechowywanie w każdym węźle wartości word_count (łącznej liczby słów w poddrzewie) pozwala pominąć całe poddrzewo, jeśli żadne słowo nie spełnia ograniczeń dotyczących długości pozostałego wzorca.
Pełna klasa WordDictionary (gotowa na rozmowę techniczną)
Przejrzysta klasa WordDictionary, gotowa do użycia na rozmowie technicznej, łącząca operację insert i wyszukiwanie z symbolem wieloznacznym kropki w jednej klasie. Jest to dokładna implementacja oczekiwana w zadaniu LeetCode 211. Rekurencyjne wyszukiwanie z funkcją any() wykorzystującą wykonanie z krótkim spięciem jest zwięzłe i jasno pokazuje osobie przeprowadzającej rozmowę mechanizm rozgałęzienia.
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.')) # FalseUżycie setdefault w kompaktowym trie
dict.setdefault(key, default) zwraca wartość dla klucza, jeśli klucz jest obecny; w przeciwnym razie wstawia wartość default i ją zwraca. Użycie node.setdefault(c, {}) w operacji insert eliminuje instrukcję if-else: tworzy słownik dziecka, jeśli go brakuje, i w każdym przypadku go zwraca. Dzięki temu operacja insert sprowadza się do przejścia w jednym wierszu: for c in word: node = node.setdefault(c, {}). To przejrzyste i zgodne ze stylem Pythona rozwiązanie.
Szybki test
Sprawdź swoje rozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji omówiono: symbol wieloznaczny '.' wymaga rozgałęzienia na wszystkie dzieci w pasującej pozycji za pomocą rekurencyjnego DFS, użycie any() z generatorem zapewnia wykonanie z krótkim spięciem i wcześniejsze zakończenie oraz setdefault umożliwia kompaktowe wykonanie operacji insert w trie w jednym wierszu. Następnie połączymy trie i backtracking, aby rozwiązać Word Search II — znaleźć wiele słów jednocześnie na planszy 2D.
Często zadawane pytania
Czy lekcja „Wyszukiwanie z symbolami wieloznacznymi i wyrażeniami regularnymi w Trie” jest bezpłatna?
Tak — pełny tekst „Wyszukiwanie z symbolami wieloznacznymi i wyrażeniami regularnymi w Trie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Wyszukiwanie z symbolami wieloznacznymi i wyrażeniami regularnymi w Trie”?
Obsługiwać dopasowanie symbolu wieloznacznego '.' przez przejście do wszystkich dzieci na danym poziomie i rozwiązywać problem design-add-and-search-words-data-structure Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Wyszukiwanie z symbolami wieloznacznymi i wyrażeniami regularnymi w Trie”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Klasa TrieNode: wstawianie i wyszukiwanie
- Wyszukiwanie prefiksów i Starts-With
- Wyszukiwanie z symbolami wieloznacznymi i wyrażeniami regularnymi w Trie
- Word Search II: Trie i przeszukiwanie z nawrotami na siatce