Алгоритм LeetCode: реализация Trie (дерево префиксов) c

2024-07-12

原题链接🔗：Реализация Trie (дерево префиксов)
трудность: Средний⭐️⭐️

тема

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

Пожалуйста, реализуйте класс Trie:

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

Пример:

входить
[«Trie», «вставить», «поиск», «поиск», «startsWith», «вставить», «поиск»]
[[], [«яблоко»], [«яблоко»], [«приложение»], [«приложение»], [«приложение»]]
выход
[ноль, ноль, правда, ложь, правда, ноль, правда]

объяснять
Trie trie = new Trie();
trie.вставить(“яблоко”);
trie.search("яблоко" // Возвращаем истину
trie.search("приложение"); // Возвращаем ложь
trie.startsWith("приложение"); // Возвращаем true
trie.вставить(“приложение”);
trie.search("приложение"); // Возвращаем истину

намекать:

1 <= длина.слова, длина.префикса <= 2000
слово и префикс состоят только из строчных английских букв
Общее количество вызовов вставки, поиска и запуска с не превышает 3*10.⁴ Второсортный

дерево префиксов

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

Характеристики префиксных деревьев：
эффективность использования пространства: Для коллекций строк с большим количеством общих префиксов деревья префиксов могут сэкономить место для хранения.
эффективность времени: временная сложность операций вставки и поиска обычно равна O(m), где m — длина строки.
динамическая коллекция: дерево префиксов может динамически вставлять и удалять строки, что подходит для сценариев, требующих частых обновлений.

Основные операции с префиксными деревьями：
вставлять: вставить строку в дерево, начиная с корневого узла и спускаясь по символу. Если дочерний узел, соответствующий символу, не существует, создайте новый узел.
поиск: поиск, существует ли строка в дереве, начиная с корневого узла и спускаясь посимвольно. Если дочерний узел символа не существует, поиск завершается неудачей.
Префиксный поиск: Проверяет, существует ли какая-либо строка с префиксом определенной строки, аналогично операции поиска, но не требует проверки конечного флага последнего узла.
удалить: Удаление строки из дерева требует рекурсивного удаления узлов, при этом гарантируя, что узлы общего префикса других строк не будут удалены.

Сценарии применения дерева префиксов：
Автозаполнение: в поисковых системах или текстовых редакторах быстро предоставляйте предложения по завершению на основе префиксов, введенных пользователем.
Проверка орфографии: проверяет правильность написания введенного пользователем слова и предлагает правильные варианты написания.
IP-маршрутизация: В сети для определения пути маршрутизации пакета используется совпадение по самому длинному префиксу.
Анализ последовательности генов: В биоинформатике используется для быстрого сопоставления и извлечения последовательностей генов.

отвечать

Идеи решения проблем：

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

Ниже приведены основные шаги и идеи решения проблем для реализации дерева Trie:

Определить узлы Trie：

Каждый узел Trie обычно содержит набор символов или логическое значение, обозначающее конец слова, а также указатели на дочерние узлы.

Инициализировать дерево：

Создайте корневой узел, который не содержит символов, но служит отправной точкой для всех слов.

операция вставки：

Начиная с корневого узла, для каждого символа вставляемой строки:
Если дочерний узел, соответствующий персонажу, не существует, создайте новый дочерний узел.
Переместите текущий узел в соответствующий дочерний узел.

Операция поиска：

Начиная с корневого узла, для каждого символа строки, которую вы хотите найти:
Если дочерний узел, соответствующий персонажу, существует, продолжайте поиск.
Если он не существует, возвращается ошибка поиска.

Префиксный поиск：

Аналогично операции поиска, но учитывается только наличие префикса строки.

Удаление операции(необязательный):

Реализуйте возможность удалять слова по мере необходимости, что обычно включает в себя удаление узлов и требует обработки счетчика ссылок узла.

Функция автозаполнения(необязательный):

Учитывая префикс, вернуть все строки, начинающиеся с этого префикса.

демо c++：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};


int main() {
    Trie trie;
    trie.insert("apple");
    std::cout << trie.search("apple") << std::endl;   // 返回 1
    std::cout << trie.search("app") << std::endl;     // 返回 0
    std::cout << trie.startsWith("app") << std::endl; // 返回 1

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

Результат вывода:

1
0
1

Код адреса склада：Трие

Обмен технологиями