Implement Trie (Prefix Tree)

Q: Dlaczego używać drzewa trie zamiast zbioru haszującego?

Zbiór haszujący odpowiada na zapytania o całe słowa w O(L) , ale nie może odpowiedzieć na pytanie o prefiks bez sprawdzenia każdego słowa. Możesz dodać drugi zbiór zawierający każdy prefiks każdego słowa, ale wtedy 20-literowe słowo będzie przechowywać 20 prefiksów o łącznej długości 210 liter. Trie przechowuje każdy wspólny prefiks tylko raz i odpowiada na oba pytania podczas tego samego przejścia. Dzięki 26 miejscom w tablicy na każdy węzeł przejście poniżej prefiksu napotyka też słowa w kolejności alfabetycznej, czego potrzebuje autouzupełnianie.

ŚrednieDrzewo trie

+10

Trie, czyli drzewo prefiksowe, przechowuje słowa, dzięki czemu szybko można sprawdzać ich początki. Zbuduj je dla słów zapisanych małymi literami i obsługujące trzy operacje: insert w dodaje słowo w, search w informuje, czy samo w zostało dodane, a startsWith p informuje, czy jakieś dodane słowo zaczyna się od p. Słowo jest swoim własnym prefiksem.

Operacje otrzymujesz w kolejności w tablicy ops, a words[i] to słowo lub prefiks dla ops[i]. Wykonaj je na jednym trie, które początkowo jest puste, i zwróć jeden ciąg znaków na każdą operację: "null" dla operacji insert oraz "true" lub "false" dla operacji search albo startsWith.

Funkcja

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: operacje, w kolejności ich wykonywania
wordsstring-array: wyraz lub prefiks dla każdej operacji
Zwracastring-array: jedna odpowiedź na operację, jako tekst

Ograniczenia

1 ≤ ops.length ≤ 2000
words.length == ops.length
Każde ops[i] to insert, search lub startsWith.
1 ≤ words[i].length ≤ 20
words[i] zawiera wyłącznie małe litery alfabetu angielskiego.

Przykłady

Wejście: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Wyjście: ["null", "false", "true", "null", "true"]
Wyjaśnienie: Na początku przechowywane jest tylko card, więc wyszukiwanie car zwraca "false": to słowo nigdy nie zostało wstawione. Jest początkiem card, więc startsWith car zwraca "true". Po wstawieniu car wyszukiwanie je znajduje.

Wejście: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Wyjście: ["null", "null", "true", "false", "false", "true", "true"]
Wyjaśnienie: Oba słowa zaczynają się od te, więc startsWith te ma wartość "true", ale żadne słowo nie jest dokładnie równe te, więc wyszukiwanie kończy się niepowodzeniem. Żadne słowo nie zaczyna się od tex. Wstawiono ten, a tea jest prefiksem samego siebie, więc dwie ostatnie odpowiedzi to "true".

Wejście: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Wyjście: ["false", "false", "null", "true", "false", "true"]
Wyjaśnienie: Trie jest początkowo pusty, więc dwie pierwsze odpowiedzi to "false". Po wstawieniu dog wyszukiwanie znajduje ten wyraz, żadne słowo nie zaczyna się od dogs, a do jest początkiem dog.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak dodać operację countPrefix p, która zwraca liczbę różnych zapisanych słów zaczynających się od p, nadal w czasie O(L)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Zbiór haszujący od razu odpowiada na pytanie search, ale startsWith pyta o każde słowo zaczynające się w określony sposób, a zbiór nie rozróżnia początków. Trie przechowuje same początki: każde słowo jest ścieżką liter od korzenia, słowa zaczynające się tak samo mają wspólny początek ścieżki, a znacznik w węźle wskazuje koniec zapisanego słowa. Na oba pytania można więc odpowiedzieć, przechodząc ścieżkę składającą się z co najwyżej L łączy, gdzie L to długość zapytania, niezależnie od liczby zapisanych słów.

Przechowuj listę słów i ją skanuj

Intuicja

Przechowuj każde dodane słowo na liście. Dla search w porównaj w z każdym zapisanym słowem. Dla startsWith p sprawdź, czy któreś zapisane słowo zaczyna się od p. W drugim przykładzie startsWith te najpierw sprawdza tea i na nim kończy; startsWith tex musi sprawdzić oba słowa, zanim zwróci "false".

To działa poprawnie i przy podanych ograniczeniach kończy działanie, ale każde zapytanie wymaga sprawdzenia wszystkich zapisanych słów. Przy n zapisanych słowach zapytanie wymaga maksymalnie n porównań po maksymalnie L liter każde. 1,000 zapisanych słów i 1,000 zapytań oznacza milion porównań ciągów znaków, a nakład pracy stale rośnie wraz ze słownikiem. Nic nie jest też współdzielone: tea i ten przechowują każde własne t i e.

Algorytm

Zacznij od pustej listy słów.
Dla insert w: dodaj w do listy.
Dla search w: zwróć informację, czy któreś zapisane słowo jest równe w.
Dla startsWith p: zwróć informację, czy któreś zapisane słowo zaczyna się od p.
Zapisz każdą odpowiedź jako tekst i zwróć listę.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

A trie: powiązania z dziećmi i flaga końca

Intuicja

Każdy węzeł drzewa trie reprezentuje jeden prefiks: litery na ścieżce od korzenia do tego węzła. Korzeń reprezentuje pusty prefiks. Węzeł przechowuje dwie rzeczy: odnośnik do węzła potomnego dla każdej litery, która może wystąpić jako następna (tablicę z 26 miejscami albo mapę przyporządkowującą litery węzłom), oraz flagę isEnd, która określa, czy zapisane słowo kończy się dokładnie w tym węźle.

insert przechodzi po słowie, zaczynając od korzenia. Dla każdej litery podąża za odnośnikiem do węzła potomnego, najpierw tworząc węzeł, jeśli brakuje odnośnika, a przy ostatniej literze ustawia isEnd. W drugim przykładzie wstawienie tea tworzy węzły dla t, te i tea oraz oznacza tea. Wstawienie ten ponownie wykorzystuje t i te, a dodaje tylko ten. Oba słowa współdzielą ścieżkę dla te — stąd nazwa „drzewo prefiksowe”.

search i startsWith wykonują tę samą wędrówkę, ale niczego nie tworzą. Jeśli brakuje odnośnika, żadne zapisane słowo nie zaczyna się od tych liter, więc obie funkcje zwracają false: tex zatrzymuje się w węźle dla te, który nie ma odnośnika dla x. Jeśli wędrówka dociera do końca, węzeł, w którym się zatrzymuje, odpowiada szukanemu prefiksowi. startsWith zwraca true, a search zwraca wartość flagi tego węzła. Węzeł dla te istnieje, ale jego flaga jest wyłączona, ponieważ słowa przechodzące przez ten węzeł kończą się niżej. Dlatego startsWith te zwraca true, a search te zwraca false.

To flaga odróżnia słowo od prefiksu. W pierwszym przykładzie po wstawieniu card istnieje ścieżka c, a, r. Bez flagi search car błędnie zwróciłoby true. Późniejsze wstawienie car nie tworzy żadnego węzła — jedynie włącza flagę.

Każda operacja przechodzi najwyżej przez L odnośników, gdzie L oznacza długość słowa, więc jej koszt wynosi O(L), niezależnie od liczby zapisanych słów. Drzewo trie przechowuje jeden węzeł dla każdego unikalnego prefiksu, nigdy więcej niż łączna liczba wstawionych liter.

Algorytm

Zdefiniuj węzeł z odsyłaczami do dzieci (26 miejsc lub mapa) i flagą isEnd, a następnie utwórz pusty korzeń.
Dla insert w: zaczynając od korzenia, podążaj za odsyłaczem dla każdej litery w, tworząc węzeł, gdy brakuje odsyłacza. Ustaw isEnd w ostatnim węźle.
Napisz funkcję pomocniczą find(p): zaczynając od korzenia, podążaj za odsyłaczem dla każdej litery p i przerwij, gdy tylko któregoś zabraknie. Zwróć osiągnięty węzeł.
Dla search w: odpowiedz true, gdy find(w) osiągnie węzeł, w którym ustawiono isEnd.
Dla startsWith p: odpowiedz true, gdy find(p) osiągnie węzeł.
Wykonaj operacje w podanej kolejności i zapisz "null", "true" lub "false" dla każdej z nich.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

Pułapki i przypadki brzegowe

Większość błędów wynika z mylenia „tu kończy się słowo” z „tędy przebiega słowo”.

Ustawianie search na wartość true zawsze, gdy istnieje ścieżka. Po wstawieniu card ścieżka dla car istnieje, ale car nigdy nie zostało wstawione.
Ustawianie isEnd tylko w nowo utworzonych węzłach. Wstawienie card po cards niczego nie tworzy, ale ostatni węzeł nadal musi mieć ustawioną flagę.
Tworzenie nowego dziecka, nawet gdy odnośnik już istnieje. To odcina wszystko, co jest w nim zapisane: wstawienie ten z nowym węzłem t powoduje utratę tea.
Zapominanie, że słowo jest swoim własnym prefiksem. Po wstawieniu tea startsWith tea zwraca true.
Odczytywanie ścieżki poza jej końcem. Prefiks dłuższy niż każde słowo, taki jak sunny, gdy zapisane jest tylko sun, musi zakończyć się na pierwszym brakującym odnośniku i zwrócić false.
Zwracanie wartości logicznych lub pomijanie wstawień w odpowiedzi. Każda operacja otrzymuje jeden ciąg znaków, w tym "null" dla wstawienia.

Najczęstsze pytania4

Jaka jest złożoność czasowa drzewa trie?

Insert, search i startsWith podążają po jednym łączu dla każdej litery argumentu, więc każda z tych operacji zajmuje O(L) czasu dla słowa o długości L, niezależnie od tego, ile słów jest przechowywanych. Trie zawiera najwyżej jeden węzeł dla każdej wstawionej litery, więc zajmuje O(T) węzłów dla łącznie T wstawionych liter, a każdy węzeł przechowuje do 26 łączy do dzieci.

Dlaczego używać drzewa trie zamiast zbioru haszującego?

Zbiór haszujący odpowiada na zapytania o całe słowa w O(L), ale nie może odpowiedzieć na pytanie o prefiks bez sprawdzenia każdego słowa. Możesz dodać drugi zbiór zawierający każdy prefiks każdego słowa, ale wtedy 20-literowe słowo będzie przechowywać 20 prefiksów o łącznej długości 210 liter. Trie przechowuje każdy wspólny prefiks tylko raz i odpowiada na oba pytania podczas tego samego przejścia. Dzięki 26 miejscom w tablicy na każdy węzeł przejście poniżej prefiksu napotyka też słowa w kolejności alfabetycznej, czego potrzebuje autouzupełnianie.

Czy węzeł drzewa trie powinien używać tablicy 26 odnośników czy mapy hashującej?

Tablica zapewnia najszybsze wyszukiwanie potomków — jeden indeks na literę — ale każdy węzeł zajmuje miejsce na 26 elementów, nawet jeśli używa tylko jednego. Mapa przechowuje tylko istniejących potomków i działa z każdym alfabetem, kosztem jednego kroku haszowania na literę. W przypadku angielskich słów zapisanych małymi literami oba rozwiązania są odpowiednie; w przypadku tekstu Unicode lub rzadkich drzew trie mapa pozwala zaoszczędzić dużo pamięci.

Gdzie w praktyce stosuje się tries?

Autouzupełnianie i podpowiedzi wyszukiwania przechodzą przez drzewo trie do wpisanego prefiksu i wyświetlają znajdujące się pod nim słowa. Korektory pisowni, gry słowne, które wyszukują na planszy słowa ze słownika, oraz routery, które znajdują najdłuższy pasujący prefiks adresu, korzystają z tej samej struktury. Gdy wiele ciągów znaków ma wspólne początki i wyszukujesz na podstawie początku, sprawdzi się drzewo trie.

Python

def trieOps(ops, words):
    # Wpisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

Oczekiwane

["null", "false", "true", "null", "true"]