Implement Trie (Prefix Tree)

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

Zbiór haszujący wyszukuje całe słowa w czasie O(L) , ale nie może odpowiedzieć na pytanie o prefiks bez przeskanowania każdego słowa. Przechowywanie każdego prefiksu w drugim zbiorze wymaga 210 liter dla jednego słowa o długości 20 liter. Trie przechowuje każdy wspólny prefiks tylko raz i odpowiada na oba pytania podczas jednego przejścia.

ŚrednieDrzewo trie

+10

Zbuduj drzewo trie (drzewo prefiksowe) dla słów zapisanych małymi literami z trzema operacjami: insert w dodaje słowo w, search w sprawdza, czy samo w zostało dodane, a startsWith p sprawdza, czy jakieś dodane słowo zaczyna się od p. Słowo jest swoim własnym prefiksem.

Operacja i to ops[i] wykonywane na words[i]. Wykonaj operacje po kolei na pustym drzewie trie i zwróć po jednym ciągu znaków dla każdej z nich: "null" dla operacji insert, "true" lub "false" dla operacji search lub startsWith.

Funkcja

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

opsstring-array: operacje w kolejności ich wykonywania
wordsstring-array: słowo 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: car jest początkiem card, więc startsWith car ma wartość "true", ale car nigdy nie zostało wstawione, więc pierwsze wyszukiwanie zwraca "false". Po insert car wyszukiwanie znajduje ten element.

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, ale żadne nie jest dokładnie równe te, więc startsWith ma wartość "true", a search — "false". Żadne słowo nie zaczyna się od tex, a tea jest swoim własnym prefiksem.

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: W pustym trie oba zapytania zwracają "false". Po insert dog wyszukiwanie znajduje ten wyraz, żadne słowo nie zaczyna się od dogs, a do jest początkiem dog.

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 obsługuje zapytanie search, ale nie ma pojęcia o początkach, więc startsWith skanowałoby każde słowo. Trie przechowuje każde słowo jako ścieżkę liter od korzenia: słowa zaczynające się tak samo dzielą ścieżkę, a flaga oznacza miejsce, w którym kończy się zapisane słowo. Oba zapytania sprowadzają się do jednego przejścia obejmującego najwyżej L łączy.

Zachowaj listę słów i przeskanuj ją

Intuicja

Przechowuj każde dodane słowo na liście. search w porównuje w z każdym przechowywanym słowem, a startsWith p sprawdza, czy którekolwiek przechowywane słowo zaczyna się od p. To poprawne rozwiązanie, ponieważ bezpośrednio sprawdza definicję. Przy n przechowywanych słowach każde zapytanie wymaga do n porównań, obejmujących do L liter: 1,000 słów i 1,000 zapytań oznacza milion porównań ciągów znaków.

Algorytm

Zacznij od pustej listy.
insert w: dodaj w na końcu.
search w: zwróć informację, czy jakieś przechowywane słowo jest równe w.
startsWith p: zwróć informację, czy jakieś przechowywane słowo zaczyna się od p.

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: odnośniki do potomków i flaga końca

Intuicja

Każdy węzeł reprezentuje jeden prefiks — litery na ścieżce od korzenia do tego węzła. Zawiera odnośnik do dziecka dla każdej litery, która może wystąpić dalej (26 miejsc lub mapa), oraz flagę isEnd, która wskazuje, czy zapisane słowo kończy się dokładnie w tym miejscu. Wstawienie tea tworzy węzły dla t, te i tea; wstawienie ten dodaje następnie tylko ten, ponieważ oba słowa mają wspólną ścieżkę dla te.

Przejście, które napotyka brakujący odnośnik, dowodzi, że żadne zapisane słowo nie zaczyna się od tych liter: tex zatrzymuje się przy te, który nie ma odnośnika do x. Przejście, które dociera do końca, znajduje się w węźle zapytania, więc startsWith ma wartość true, a search zwraca wartość flagi. Węzeł dla te istnieje, ale jego flaga jest wyłączona, więc search te zwraca false. Każda operacja przechodzi przez co najwyżej L odnośników, niezależnie od liczby zapisanych słów, a trie zawiera jeden węzeł na każdy odrębny prefiks.

Algorytm

Utwórz korzeń bez łączy do dzieci i z wyłączonym isEnd.
insert w: zaczynając od korzenia, podążaj za łączem dla każdej litery, tworząc węzeł, jeśli go brakuje. Ustaw isEnd w ostatnim węźle.
find(p): zaczynając od korzenia, podążaj za łączem dla każdej litery; zwróć nic, gdy tylko któregoś zabraknie, w przeciwnym razie zwróć osiągnięty węzeł.
search w: prawda, gdy find(w) zwraca węzeł z ustawionym isEnd.
startsWith p: prawda, gdy find(p) zwraca węzeł.

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

Sprawienie, by search zwracało true zawsze, gdy istnieje ścieżka. Po insert card ścieżka dla car istnieje, ale search car musi zwracać false.
Ustawianie isEnd tylko w nowo utworzonych węzłach. Wstawienie card po cards niczego nie tworzy, ale ostatni węzeł potrzebuje swojej flagi.
Tworzenie nowego dziecka, gdy połączenie już istnieje. Wstawienie ten z nowym węzłem t powoduje utratę tea.
Odczytywanie poza koniec ścieżki. startsWith sunny, gdy zapisano tylko sun, musi zatrzymać się przy pierwszym brakującym połączeniu i zwrócić false.

Najczęstsze pytania3

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

Wstawianie, wyszukiwanie i startsWith podążają za jednym łączem na każdą literę, więc każde z nich zajmuje O(L) dla słowa o długości L, niezależnie od liczby przechowywanych słów. Wymagana przestrzeń to O(T) węzłów dla łącznie T wstawionych liter, przy czym każdy węzeł przechowuje do 26 łączy do dzieci.

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

Zbiór haszujący wyszukuje całe słowa w czasie O(L), ale nie może odpowiedzieć na pytanie o prefiks bez przeskanowania każdego słowa. Przechowywanie każdego prefiksu w drugim zbiorze wymaga 210 liter dla jednego słowa o długości 20 liter. Trie przechowuje każdy wspólny prefiks tylko raz i odpowiada na oba pytania podczas jednego przejścia.

Czy węzeł trie powinien używać tablicy 26 łączy czy mapy haszującej?

Tablica znajduje dziecko za pomocą jednego indeksu, ale zajmuje 26 miejsc na węzeł, nawet jeśli węzeł ma tylko jedno dziecko. Mapa przechowuje tylko istniejące dzieci i działa dla dowolnego alfabetu, kosztem obliczenia skrótu dla każdej litery. W przypadku małych liter alfabetu angielskiego sprawdzą się oba rozwiązania; w przypadku Unicode lub rzadkich drzew trie mapa oszczędza pamięć.

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

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

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