(Решение проблемы среды LeetCode)
https://leetcode.com/problems/implement-trie-prefix-tree/

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

Trie — это специальная структура данных, используемая для хранения строк, которые можно визуализировать как график. Он состоит из узлов и ребер. Каждый узел состоит максимум из 26 дочерних элементов, а ребра соединяют каждый родительский узел с его дочерними элементами.

Здесь мы видим, что вставили четыре слова «A», «AMY», «AND» и «ANY», поэтому узлы, показанные зеленым цветом, являются концом слова. Рассмотрим еще один пример.

Здесь мы видим, что вставили четыре слова «ПН», «ВТ», «СР» и «МЫ», поэтому узлы, показанные зеленым цветом, являются концом слова.

Список операций, выполняемых над префиксом Trie.

  • insert(word): добавляет новое слово.
  • search(word): проверяет, есть ли в Trie заданное слово.
  • найти(префикс): возвращает все слова с заданным префиксом (начинается с).

При создании узла нам нужно будет проверить, является ли этот узел концом данного слова, если это так, мы пометим isEndOfWord как истину, при поиске слова мы проверим, находится ли искомое слово в словарь или нет, он будет проверен, только если isEndOfWord вернет true.

Давайте посмотрим, как написать код для того же самого.

// creat
var TrieNode = function() {
    this.children = {};
    this.isEndOfWord = false;
}

var Trie = function() {
    this.root = new TrieNode();
};

Trie.prototype.insert = function(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
        const char = word.charAt(i);
        if (!(char in node.children)) {
            node.children[char] = new TrieNode();
        }
        node = node.children[char];
    }
    node.isEndOfWord = true;
};

Trie.prototype.search = function(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
        const char = word.charAt(i);
        if (!(char in node.children)) {
            return false;
        }
        node = node.children[char];
    }

    return node.isEndOfWord;
};

Trie.prototype.startsWith = function(prefix) {
    let node = this.root;
    for (let i = 0; i < prefix.length; i++) {
        const char = prefix.charAt(i);
        if (!(char in node.children)) {
            return false;
        }
        node = node.children[char];
    }
    return true;
};

Временная сложность структуры данных trie

Временная сложность поиска и вставки из дерева зависит от длины искомого и вставляемого слова.
Временная сложность: O(a * n) .

общее количество слов: n,
средняя длина каждого слова: a,

При поиске слов с заданным префиксом.
Временная сложность: O(p + n)

общее количество слов: n,
длина префикса: p

Пространственная сложность структуры данных trie

Как мы знаем, каждый узел может иметь 26 ссылок (если рассматривать строки, содержащие только английский алфавит), это число может увеличиваться, если числовое, а также добавляются специальные значения.

Пространственная сложность O(n * k)

k - количество ссылок, хранимых каждым узлом (26 для английского алфавита)

Надеюсь, это поможет вам четко понять, как создать структуру данных Trie. А пока продолжайте кодить и продолжайте учиться!

Оставайтесь с нами, чтобы не пропустить новые блоги! 💻