Реализация тройки

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

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

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



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

Оцените статью
devanswers.ru
Добавить комментарий