Wyszukiwanie prefiksów i Starts-With
Dodawać metodę starts_with, która zwraca true, jeśli którekolwiek wstawione słowo ma dany prefiks, i używać jej do implementacji sugestii autouzupełniania
Wyszukiwanie prefiksów i Starts-With to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 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.
Możliwości zapytań o prefiksy
Najważniejszą przewagą trie nad mapą haszującą jest wydajne wyszukiwanie prefiksów. Zapytanie o prefiks odpowiada na pytania: „ile zapisanych słów zaczyna się od tego prefiksu?”, „jakie są wszystkie zapisane słowa z tym prefiksem?” lub po prostu „czy istnieje słowo z tym prefiksem?”. Zapytania te zajmują O(p), gdzie p to długość prefiksu, niezależnie od całkowitej liczby zapisanych słów — dzięki temu trie doskonale nadaje się do autouzupełniania i podpowiedzi wyszukiwania.
Metoda starts_with
starts_with(prefix) zwraca True, jeśli którekolwiek zapisane słowo zaczyna się od podanego prefiksu. Należy przejść przez trie, podążając za każdym znakiem prefiksu. Jeśli można przejść za wszystkimi znakami bez napotkania brakującej krawędzi, prefiks istnieje, a co najmniej jedno słowo się od niego zaczyna. Implementacja jest identyczna jak w przypadku search, z wyjątkiem tego, że po zakończeniu przejścia zwracamy True — nie sprawdzamy is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(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 starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # FalseAutouzupełnianie: znajdowanie wszystkich słów z prefiksem
Aby zaimplementować autouzupełnianie, należy przejść do węzła kończącego prefiks, a następnie wykonać DFS (lub BFS) od tego węzła, aby zebrać wszystkie słowa rozgałęziające się z tej ścieżki. Do każdego zebranego przyrostka należy dodać prefiks, aby odtworzyć pełne słowa. Jest to operacja O(p + W), gdzie W to łączna liczba znaków we wszystkich pasujących słowach.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(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 autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return []
node = node.children[c]
# DFS from prefix end node
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for char, child in n.children.items():
dfs(child, path + char)
dfs(node, '')
return results
t = Trie()
for w in ['apple','app','application','apply','apt']:
t.insert(w)
print(t.autocomplete('app')) # ['app','apple','apply','application']Zwracanie posortowanych podpowiedzi
W przypadku posortowanego autouzupełniania podczas DFS należy przechodzić przez węzły potomne w kolejności alfabetycznej (iterując po sorted(node.children.items())). Ponieważ węzły potomne są przechowywane w słowniku, dodaje to narzut O(ALPHABET_SIZE × depth), ale gwarantuje wyniki uporządkowane leksykograficznie. Trie oparte na tablicy zawsze przechodzi przez węzły potomne w kolejności alfabetycznej, ponieważ indeksy od 0 do 25 są uporządkowane.
def dfs_sorted(node, prefix, results):
if node.is_end:
results.append(prefix)
for char in sorted(node.children.keys()): # alphabetical order
dfs_sorted(node.children[char], prefix + char, results)
print('Iterating children in sorted order gives lex-sorted suggestions')Podpowiedzi autouzupełniania Top-K
Aby uzyskiwać k najczęściej wybieranych podpowiedzi, należy rozszerzyć każdy węzeł o licznik określający, ile razy wyszukiwano słowo kończące się w tym węźle. Podczas zbierania podpowiedzi należy użyć kopca maksymalnego o rozmiarze k. Ogranicza to wynik zbierania DFS z O(W) do O(k), bez materializowania wszystkich dopasowań. Rzeczywiste wyszukiwarki łączą przechodzenie po prefiksie trie z danymi o częstotliwości, aby szybko dostarczać trafne podpowiedzi.
Implementacja trie dla LeetCode 208
LeetCode 208 „Implement Trie (Prefix Tree)” wymaga dokładnie metod: insert(word), search(word) zwracającej wartość logiczną informującą o dokładnym dopasowaniu oraz startsWith(prefix) zwracającej wartość logiczną informującą o dopasowaniu prefiksu. Jest to kanoniczna implementacja trie. Należy pamiętać: search wymaga is_end=True, natomiast startsWith wymaga tylko istnienia ścieżki prefiksu.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = True # '#' marks word end
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return '#' in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return True
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False
print(t.startsWith('app')) # TrueUżycie „#” jako znacznika końca (trie ze słownikiem)
Elegancki skrót polega na przechowywaniu trie jako zagnieżdżonych słowników ze specjalnym kluczem wartownika, takim jak '#', oznaczającym końce słów. Eliminuje to potrzebę korzystania z klasy TrieNode. Takie rozwiązanie jest zwięzłe i wygodne podczas rozmów technicznych, ale nieco mniej czytelne niż jawne obiekty TrieNode. Obie implementacje są poprawne; wersję ze słownikami szybciej można napisać pod presją czasu.
Najdłuższy wspólny prefiks z użyciem trie
Aby znaleźć najdłuższy wspólny prefiks listy napisów, należy wstawić wszystkie napisy do trie, a następnie przechodzić od korzenia pojedynczą ścieżką, która istnieje tak długo, jak długo spełnione są warunki: (1) bieżący węzeł ma dokładnie jedno dziecko oraz (2) is_end ma wartość False. Należy zatrzymać się, gdy którykolwiek z tych warunków przestanie być spełniony. Przejście tą ścieżką wyznacza najdłuższy wspólny prefiks.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def longest_common_prefix(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.is_end = True
prefix = []
node = root
while len(node.children) == 1 and not node.is_end:
char, node = next(iter(node.children.items()))
prefix.append(char)
return ''.join(prefix)
print(longest_common_prefix(['flower','flow','flight'])) # 'fl'
print(longest_common_prefix(['dog','racecar','car'])) # ''Problem Replace Words
Replace Words (LeetCode 648): mając słownik słów bazowych i zdanie, należy zastąpić każde słowo w zdaniu najkrótszym pasującym słowem bazowym ze słownika. Wszystkie słowa bazowe należy wstawić do trie. Dla każdego słowa w zdaniu należy przechodzić przez trie aż do znalezienia końca słowa bazowego, a następnie zwrócić ten rdzeń jako zamiennik. Jeśli żaden rdzeń nie pasuje, należy pozostawić oryginalne słowo. Złożoność wynosi O(total chars), zamiast O(n × m) w rozwiązaniu naiwnym.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def replaceWords(dictionary, sentence):
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def find_root(word):
node = root
for i, c in enumerate(word):
if c not in node.children: break
node = node.children[c]
if node.is_end:
return word[:i+1]
return word
return ' '.join(find_root(w) for w in sentence.split())
print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))Problem Map Sum Pairs
Map Sum (LeetCode 677): należy wstawiać pary klucz-wartość i zwracać sumę wszystkich wartości, których klucze mają podany prefiks. Każdy obiekt TrieNode należy rozszerzyć o pole val. Podczas wstawiania należy przejść do końca klucza i ustawić wartość; w przypadku zapytań sumujących należy przejść do węzła kończącego prefiks i zsumować metodą DFS wszystkie pola val znajdujące się poniżej. Alternatywnie podczas wstawiania można przechowywać w każdym węźle sumę skumulowaną, aby wykonywać zapytania w czasie O(p).
Implementowanie autouzupełniania z ograniczoną liczbą wyników
W produkcyjnych systemach autouzupełniania zwracanie wszystkich słów pasujących do prefiksu jest niepraktyczne, gdy pasują tysiące słów. Zamiast tego podczas przechodzenia DFS należy użyć kopca maksymalnego o rozmiarze k: przechowywać k najwyżej ocenionych słów znalezionych do tej pory. Gałęzie DFS należy kończyć wcześniej, jeśli nie mogą zawierać słowa należącego do najlepszych k wyników (przycinanie na podstawie górnego ograniczenia wyniku). Daje to złożoność O(p + k × log k) na zapytanie dla k sugestii — znacznie lepszą niż zebranie wszystkich dopasowań.
Szybki test
Sprawdź swoje rozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji omówiono: starts_with przechodzi ścieżkę prefiksu i zwraca True, jeśli ona istnieje — nie jest potrzebne sprawdzenie is_end, DFS autouzupełniania zbiera wszystkie słowa od węzła kończącego prefiks, dopisując znaki podczas schodzenia w dół oraz rozszerzenie węzłów o liczniki lub wartości umożliwia wykonywanie zapytań sumujących i zwracanie k najlepszych sugestii. Następnie do trie dodamy dopasowywanie symboli wieloznacznych i wyrażeń regularnych.
Często zadawane pytania
Czy lekcja „Wyszukiwanie prefiksów i Starts-With” jest bezpłatna?
Tak — pełny tekst „Wyszukiwanie prefiksów i Starts-With” 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 prefiksów i Starts-With”?
Dodawać metodę starts_with, która zwraca true, jeśli którekolwiek wstawione słowo ma dany prefiks, i używać jej do implementacji sugestii autouzupełniania Ć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 2 z 4.
Ile czasu zajmuje lekcja „Wyszukiwanie prefiksów i Starts-With”?
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