Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.6 kB
3
Indexable
class Trie {
public:
    unordered_map<char, Trie*> next;
    bool isWordEnding;

    Trie(): isWordEnding(false) {}

    void insert(string& word) {
        Trie* node = this;
        for (auto &ch: word) {
            if (node->next.find(ch) == node->next.end()) {
                node->next[ch] = new Trie();
            }
            node = node->next[ch];
        }
        node->isWordEnding = true;
    }
};

class StreamChecker {
private:
    Trie* trie;
    vector<Trie*> parallelSearches;
public:
    StreamChecker(vector<string>& words): trie(new Trie()) {
        for (auto& word: words) {
            trie->insert(word);
        }
    }
    
    bool query(char letter) {
        Trie* root = trie;
        if (root->next.find(letter) != root->next.end()) {
            parallelSearches.push_back(root);
        }

        parallelSearches.erase(remove_if(
            parallelSearches.begin(), parallelSearches.end(),
            [&letter](Trie* search) {
                return search->next.find(letter) == search->next.end();
            }), parallelSearches.end());

        transform(parallelSearches.begin(), parallelSearches.end(), parallelSearches.begin(), [&letter](Trie* search) {
            return search->next[letter];
        });

        return accumulate(parallelSearches.begin(), parallelSearches.end(), false, [](bool result, Trie* search) {
            return search->isWordEnding or result;
        });
    }
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */