0Pricing
Coding Interview Prep · Lekcja

Trie do wyszukiwania prefiksów

Szybkie przechowywanie i wyszukiwanie prefiksów słów

Trie do wyszukiwania prefiksów to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 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.

Sprytne przechowywanie słów

Trie to drzewo przechowujące słowa przez współdzielenie wspólnych prefiksów. Dzięki niemu zapytania o prefiksy są błyskawiczne. 🌳

Dlaczego nie wystarczy zbiór

Zbiór umożliwia wyszukiwanie całych słów, ale trie obsługuje także zapytania o prefiks, na przykład: czy jakiekolwiek słowo zaczyna się od pre.

Wierzchołki i krawędzie

Każdy wierzchołek oznacza pozycję w pewnym słowie, a każda krawędź jest opisana znakiem znajdującym się na ścieżce od korzenia.

Dzieci jako słownik

W Pythonie najprostszy wierzchołek to słownik mapujący znak na jego wierzchołek potomny. To przejrzyste i elastyczne rozwiązanie.

root = {}

Wstawianie słowa

Aby wstawić słowo, należy przechodzić po kolejnych znakach i tworzyć potomka za każdym razem, gdy go brakuje.

node = root
for c in word:
    node = node.setdefault(c, {})

Oznaczanie końców słów

Po wstawieniu należy ustawić flagę end, aby odróżnić całe słowo od samego prefiksu.

node['#'] = True

Wyszukiwanie całego słowa

Aby wyszukać słowo, należy przejść po jego znakach; jeśli zabraknie któregokolwiek kroku, słowo nie występuje. Następnie trzeba sprawdzić flagę końca.

for c in word:
    if c not in node:
        return False
    node = node[c]

Sprawdzanie prefiksu

Zapytanie o prefiks przebiega tak samo, ale pomija sprawdzanie flagi końca. Dotarcie do ostatniego wierzchołka oznacza odpowiedź twierdzącą.

Złożoność czasowa

Wstawianie i wyszukiwanie kosztują O(L), gdzie L to długość słowa, niezależnie od liczby przechowywanych słów. Liczy się długość.

Liczenie słów według prefiksu

Należy przechowywać licznik w każdym wierzchołku, aby natychmiast odpowiadać na pytania o liczbę przechowywanych słów ze wskazanym prefiksem.

Gdzie przydają się drzewa trie

Drzewa trie obsługują autouzupełnianie, sprawdzanie słowników i problemy z maksymalnym XOR-em dla bitów. To podstawa wielu konkursowych zadań tekstowych.

Szybkie sprawdzenie

Należy upewnić się, jaki jest rzeczywisty koszt wyszukiwania w drzewie trie.

Podsumowanie: drzewa trie opanowane

Można już budować drzewo trie, wstawiać i wyszukiwać w O(L), a także szybko obsługiwać zapytania o prefiksy i ich liczność. 🌟

Często zadawane pytania

Czy lekcja „Trie do wyszukiwania prefiksów” jest bezpłatna?

Tak — pełny tekst „Trie do wyszukiwania prefiksów” 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 „Trie do wyszukiwania prefiksów”?

Szybkie przechowywanie i wyszukiwanie prefiksów słów Ć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 4 z 4.

Ile czasu zajmuje lekcja „Trie do wyszukiwania prefiksów”?

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

  1. Funkcja prefiksowa KMP
  2. Wielomianowe haszowanie napisów
  3. Funkcja Z do wyszukiwania wzorców
  4. Trie do wyszukiwania prefiksów
← Powrót do Coding Interview Prep