Trie (произносится как «попробуй») или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и извлечения ключей в наборе данных строк. Существуют различные приложения этой структуры данных, такие как автозаполнение и проверка орфографии.

Реализуйте класс Trie:

Trie() Инициализирует объект trie.
void insert(String word) Вставляет строковое слово в trie.
boolean search(String word) Возвращает true, если строковое слово находится в дереве (т. е. было вставлено ранее), и false в противном случае.
boolean startsWith(String prefix) Возвращает true, если есть ранее вставленное строковое слово с префиксом префикса, и false в противном случае.


class TrieNode():
    def __init__(self):
        self.children = {}
        self.endOfWord = False

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

    def insert(word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.endOfWord = True

    def search(word):
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.endOfWord

    def startsWith(prefix):
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True



Войти в полноэкранный режим

Выйти из полноэкранного режима