Задача: 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. Найдите максимальную сумму для каждого случая.

😎 Решение:

public class TrieNode {
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsEndOfWord = false;
}

public class StreamChecker {
    private TrieNode root;
    private LinkedList<char> stream;

    public StreamChecker(string[] words) {
        root = new TrieNode();
        stream = new LinkedList<char>();
        foreach (var word in words) {
            var node = root;
            for (int i = word.Length - 1; i >= 0; i--) {
                if (!node.Children.ContainsKey(word[i])) {
                    node.Children[word[i]] = new TrieNode();
                }
                node = node.Children[word[i]];
            }
            node.IsEndOfWord = true;
        }
    }

    public bool Query(char letter) {
        stream.AddFirst(letter);
        var node = root;
        foreach (var char in stream) {
            if (!node.Children.ContainsKey(char)) return false;
            node = node.Children[char];
            if (node.IsEndOfWord) return true;
        }
        return false;
    }
}

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