Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium

Реализуйте структуру данных Trie (префиксное дерево), поддерживающую следующие операции:
insert(word) — вставка слова
search(word) — проверка, было ли слово вставлено
startsWith(prefix) — проверка, начинается ли хоть одно вставленное слово с заданного префикса

Пример:

Input: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output: [null, null, true, false, true, null, true]

👨‍💻 Алгоритм:

1⃣Инициализация и вставка:
Каждый узел (TrieNode) содержит массив из 26 указателей (по одной на каждую букву алфавита) и флаг isEnd.
Метод insert создает недостающие узлы и в конце устанавливает isEnd = true для последнего символа слова.

2⃣Поиск строки:
Метод search использует вспомогательную функцию searchPrefix, которая проходит по всем символам слова. Если найденный узел существует и отмечен как конец слова, возвращаем true.

3⃣Проверка префикса:
Метод startsWith использует searchPrefix, и возвращает true, если удалось дойти до конца заданного префикса.

😎 Решение:

#include <vector>
#include <string>

class TrieNode {
private:
    TrieNode* links[26];
    bool isEnd;

public:
    TrieNode() : isEnd(false) {
        for (int i = 0; i < 26; ++i) {
            links[i] = nullptr;
        }
    }

    bool containsKey(char ch) {
        return links[ch - 'a'] != nullptr;
    }

    TrieNode* get(char ch) {
        return links[ch - 'a'];
    }

    void put(char ch, TrieNode* node) {
        links[ch - 'a'] = node;
    }

    void setEnd() {
        isEnd = true;
    }

    bool isEndNode() {
        return isEnd;
    }
};

class Trie {
private:
    TrieNode* root;

    TrieNode* searchPrefix(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->containsKey(ch)) {
                node = node->get(ch);
            } else {
                return nullptr;
            }
        }
        return node;
    }

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->containsKey(ch)) {
                node->put(ch, new TrieNode());
            }
            node = node->get(ch);
        }
        node->setEnd();
    }

    bool search(const std::string& word) {
        TrieNode* node = searchPrefix(word);
        return node != nullptr && node->isEndNode();
    }

    bool startsWith(const std::string& prefix) {
        return searchPrefix(prefix) != nullptr;
    }
};

Ставь 👍 и забирай 📚 Базу знаний