Задача: 1032. Stream of Characters
Сложность: hard

Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words.

Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words.

Пример:

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

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

1⃣Построение суффиксного Trie:
Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов.

2⃣Проверка суффиксов:
Для каждого нового символа, проходите по текущему списку символов и проверяйте, образуют ли они какой-либо суффикс, присутствующий в Trie. Если найдено совпадение, возвращайте true, иначе продолжайте добавлять новые символы и проверять суффиксы.

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class TrieNode {
public:
    TrieNode* children[26] = {};
    bool is_end_of_word = false;
};

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        for (const string& word : words) {
            TrieNode* node = root;
            for (int i = word.size() - 1; i >= 0; --i) {
                if (!node->children[word[i] - 'a']) {
                    node->children[word[i] - 'a'] = new TrieNode();
                }
                node = node->children[word[i] - 'a'];
            }
            node->is_end_of_word = true;
        }
    }
    
    bool query(char letter) {
        stream.push_front(letter);
        TrieNode* node = root;
        for (char c : stream) {
            if (!node->children[c - 'a']) return false;
            node = node->children[c - 'a'];
            if (node->is_end_of_word) return true;
        }
        return false;
    }

private:
    TrieNode* root;
    deque<char> stream;
};

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