1032. Stream of Characters

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;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TrieNode {
    public unordered_map<char, TrieNode> Children = new unordered_map<char, TrieNode>();
    public bool IsEndOfWord = false;
}
public class StreamChecker {
    private TrieNode root;
    private LinkedList<char> stream;
    public StreamChecker(vector<string> words) {
        root = new TrieNode();
        stream = new LinkedList<char>();
        foreach (var word in words) {
            var node = root;
            for (int i = word.size() - 1; i >= 0; i--) {
                if (!node.Children.count(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.count(char)) return false;
            node = node.Children[char];
            if (node.IsEndOfWord) return true;
        }
        return false;
    }
}

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

public class StreamChecker {
    private TrieNode root;
    private StringBuilder stream;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        stream = new StringBuilder();
        for (String word : words) {
            TrieNode node = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                char ch = word.charAt(i);
                node = node.children.computeIfAbsent(ch, k -> new TrieNode());
            }
            node.isEndOfWord = true;
        }
    }

    public boolean query(char letter) {
        stream.insert(0, letter);
        TrieNode node = root;
        for (int i = 0; i < stream.length(); i++) {
            char ch = stream.charAt(i);
            if (!node.children.containsKey(ch)) return false;
            node = node.children.get(ch);
            if (node.isEndOfWord) return true;
        }
        return false;
    }
}

Algorithm

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

😎