208. Реализовать трие (префиксное дерево) 🚀



Решение разработано в:

Вопрос

В этой статье мы рассмотрим вопрос Leetcode ‘208. Реализовать трие (префиксное дерево)».

Вопрос:

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

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

  • void insert(String word) Вставляет строку word в трие.
  • boolean search(String word) Возвращает true, если строковое слово находится в тройке (т.е. было вставлено ранее), и false в противном случае.
  • boolean startsWith(String prefix) Возвращает true, если существует ранее вставленное строковое слово с префиксом prefix, и false иначе.Пример:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Вход в полноэкранный режим Выход из полноэкранного режима

Объяснение вопроса

Этот вопрос оценивается как средний. Что по большей части соответствует действительности. Но он является средним ТОЛЬКО в том случае, если вы уже знаете, что такое Trie / префиксное дерево.

Нас просят реализовать структуру данных Trie. Которую я буду называть префиксным деревом. Что это такое, смотрите ниже.


Что такое трие?

Тройка — это древовидная структура данных, которая используется для эффективного хранения и извлечения ключей в наборе данных строк. Существуют различные применения этой структуры данных, например, автозаполнение и проверка орфографии. Как вы думаете, почему Google так быстро выдает предложения о том, что вы ищете? Как проверка орфографии может иметь представление о том, что вы ищете?

Ответ заключается в том, что у них есть Trie (префиксное дерево). Это означает, что существует древовидная структура, в которой хранятся все префиксы для всех слов, которые вы ищете. Посмотрите на изображение ниже:

Обратите внимание, что App и Apple находятся на одном и том же пути дерева. Разница лишь в том, что App является префиксом Apple, и поэтому конец App отмечен красным цветом, так как это означает конец слова. То же самое с буквой E, так как это конец Apple. Префиксное дерево создает дерево для каждого префикса слова.

Почему же это так необычно?
Потому что это невероятно быстро. На каждый искомый символ вы отсеиваете множество слов. Так, если вы ищете слово, начинающееся на букву А, вы отсеиваете все слова, которые НЕ начинаются на А.

Это также дает нам возможность запрашивать слова и их префиксы, что часто используется в динамическом программировании для решения проблем, связанных со строками.

Рекомендуемые знания

  1. Деревья
  2. Trie
  3. Объектно-ориентированный JS

Что мы знаем?

  1. Нам нужно создать префиксное дерево
  2. Нам нужно уметь создавать его, вставлять слово, искать слово и искать префикс.

Как мы это сделаем:

Сначала мы определим TrieNode, так как это будет ключом к реализации трие.

class TrieNode {
    constructor(children = {}, end_of_word = false) {
        // Our child is a hashmap of chars.
        // Which we will use to ask.
        // -  "Does this node have a child with this char?" and
        // -  "Is this the end of a word?"

        this.children    = children;
        this.end_of_word = end_of_word;
    }
}
Вход в полноэкранный режим Выйти из полноэкранного режима

Посмотрите, что у нас есть свойство children. Это хэшмап. Каждый узел будет содержать хэш-карту дочерних элементов. То есть, у каждого узла мы можем спросить: «Есть ли у этого узла ребенок?». У нас также есть свойство end_of_word. Это булево значение. Мы будем использовать его, чтобы определить, достигли ли мы конца слова. Поэтому, когда мы вставим слово, мы установим свойство end_of_word в true на последнем узле.

  1. Для инициализации тройки мы будем использовать конструктор TrieNode. Это даст нам this.root, который является TrieNode. Он будет выступать в качестве главы всего дерева.
  2. Мы начнем со вставки слова. Мы разбиваем слово на массив символов. Затем мы спрашиваем текущий узел «Есть ли у вас дочерний элемент с таким char?». Если да, то мы переходим к нему, если нет, то создаем новый узел и добавляем его к дочерним. Как только мы достигли конца слова, мы устанавливаем свойство end_of_word в true.
  3. Для поиска мы сделаем что-то похожее на вставку. Мы разбиваем слово на массив символов. Затем мы спрашиваем текущий узел «Есть ли у вас дочерний элемент с таким char?». Если да, мы переходим к нему, если нет — возвращаем false. Когда мы достигли конца слова, мы спрашиваем: «Теперь мы в конце слова, действительно ли я в конце слова?» Если да, мы возвращаем true. Для этого мы спрашиваем узел, истинно ли его свойство node.
  4. Функция SearchWith аналогична функции .3, но вместо запроса конечного узла мы просто возвращаем true, в противном случае мы возвращаем false, если char не существует.

Нотация Big O:

  • Временная сложность: O(c)| Где c — количество символов в слове. Поскольку нам придется пройтись по дереву для каждого символа. Возможно, это O(n), поскольку мы должны пройти все дерево для каждого символа в случае, если в дереве только 1 слово.
  • Пространственная сложность: O(b)| Где b — количество символов в слове. Поскольку в худшем случае нам придется создавать новый узел для каждого символа в слове.

Решение

class TrieNode {
    constructor(child = {}, end = false) {

        // Our child is a hashmap of chars.
        // Which we will use to ask.
        // -  "Does this node have a child with this char?" and
        // -  "Is this the end of a word?"
        this.child = child;
        this.end   = end;
    }
}

var Trie = function () {

    // Set root node, just like Binary Trees
    this.root = new TrieNode();
};

Trie.prototype.insert = function (word) {

    // Get a handle on the root node
    // As we're inserting a word, we'll need to traverse the tree
    let current = this.root;

    // Fancy for loop, go over each word,
    // if it already exists, traverse it, if not
    // create it. 
    for (const char of word) {
        if (!current.child[char]) {
            current.child[char] = new TrieNode();
        }
        current = current.child[char];
    }

    current.end = true;
};

Trie.prototype.search = function (word) {

    // Get a handle on the root node
    let current = this.root;

    // Fancy for loop, go over each word,
    // if it already exists, traverse it, if not return false
    for (const char of word) {
        if (current.child[char]) {
            current = current.child[char];
        } else {
            return false;
        }
    }

    // Is this the end of a word?
    return current.end;
};

Trie.prototype.startsWith = function (prefix) {

    // Get a handle on the root node
    let current = this.root;

    // Fancy for loop, go over each word,
    // if it already exists, traverse it, if not return false
    for (const char of prefix) {
        if (current.child[char]) {
            current = current.child[char];
        } else {
            return false;
        }
    }

    // Well we made it this far, so it must be true. :D
    return true;
};
Войдите в полноэкранный режим Выйти из полноэкранного режима

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