Trie in C++

Leetcode 1032. Stream of Characters

Problem

1032. Stream of Characters

Solutions

Tie data structure illustration. Image source [1]

A straightforward trie got TLE

struct vertex {
    char alphabet;
    bool exist;
    vector<vertex*> child;
    vertex(char a): alphabet(a), exist(false) {
        child.assign(26, nullptr);
    }
};
class Trie {
    public:
    vertex* root;
   
    Trie() {root = new vertex('!'); }
    void insert(string word) {
        vertex* curr = root;
        for (int i = 0; i < (int) word.size(); ++i) {
            int alphaNum = word[i] - 'a';
            if (curr->child[alphaNum] == nullptr) {
                curr->child[alphaNum] = new vertex(word[i]);
            }
            curr = curr->child[alphaNum];
        }
        curr->exist = true;
    }
};
class StreamChecker {
    Trie trie;
    vector<vertex*> history;
public:
    StreamChecker(vector<string>& words) {
        for (auto word : words) {
            trie.insert(word);
        }
        history.push_back(trie.root);
    }
    
    bool query(char letter) {
        int alphaNum = letter - 'a';
        bool ret = false;
        vector<vertex*> new_history;
        new_history.push_back(trie.root);
        for (auto his : history) {
            if (his->child[alphaNum] && his->child[alphaNum]->exist) {
                ret = true;
            } 
            if (his->child[alphaNum]) {
                new_history.push_back(his->child[alphaNum]);
            }
        }
        history = move(new_history);
        return ret;
    }
};
/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */

How to get rid of TLE?

The problem is we don’t know how many characters to match. On the example above, should we try to match the last three stream characters “jkl”, the last two “kl”, or the last one “l”?

The way to solve the problem is to notice that we always know the last character to match. That gives us an idea to build a trie of reversed words, and try to match the reversed stream of characters. from [1]

Trie of the reversed words and the reversed stream of characters.[1]

C++ code

struct vertex {
    char alphabet;
    bool exist;
    vector<vertex*> child;
    vertex(char a): alphabet(a), exist(false) {
        child.assign(26, nullptr);
    }
};
class Trie {
    public:
    vertex* root;
   
    Trie() {root = new vertex('!'); }
    void insert(string word) {
        vertex* curr = root;
        for (int i = 0; i < (int) word.size(); ++i) {
            int alphaNum = word[i] - 'a';
            if (curr->child[alphaNum] == nullptr) {
                curr->child[alphaNum] = new vertex(word[i]);
            }
            curr = curr->child[alphaNum];
        }
        curr->exist = true;
    }
};
class StreamChecker {
    Trie trie;
    string history = "";
public:
    StreamChecker(vector<string>& words) {
        for (auto word : words) {
            reverse(word.begin(), word.end());
            trie.insert(word);
        }
    }
    
    bool query(char letter) {
        history += letter;
        auto curr = trie.root;
        for (int i = history.size() - 1; i >= 0; --i) {
            int alphaNum = history[i] - 'a';
            if (curr->child[alphaNum] != nullptr) {
                if (curr->child[alphaNum]->exist) return true;
                else curr = curr->child[alphaNum];
            }
            else return false;
        }
        return false;
    }
};
/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */

We can also put all operations in the trie data structure

struct vertex {
    char alphabet;
    bool exist;
    vector<vertex*> child;
    vertex(char a) : alphabet(a), exist(false) {
        child.assign(26, nullptr);
    }
};
class Trie {
    private:
    vertex* root;
    public:
    Trie() {
        root = new vertex('!');
    }
    void insert(string word) {
        vertex* curr = root;
        for (int i = 0; i < (int)word.size(); ++i) {
            int alphaNum = word[i] - 'a';
            if (curr->child[alphaNum] == nullptr) {
                curr->child[alphaNum] = new vertex(word[i]);
            }
            curr = curr->child[alphaNum];
        }
        curr->exist = true;   
    }
    bool query(string& history) {
        vertex* curr = root;
        for (int i = history.size() - 1; i >= 0; --i) {
            int alphaNum = history[i] - 'a';
            if (curr->child[alphaNum] != nullptr) {
                if (curr->child[alphaNum]->exist) return true;
                else curr = curr->child[alphaNum];
            }
            else return false;
        }
        return false;
    }
};
class StreamChecker {
private:
    Trie trie;
    string history;
public:
    StreamChecker(vector<string>& words) {
        //history = "";
        for (auto word :  words) {
            reverse(word.begin(), word.end());
            trie.insert(word);
        }
    }
    
    bool query(char letter) {
        history += letter;
        return trie.query(history);
        
    }
};
/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */

Reference

[1]https://leetcode.com/problems/stream-of-characters/solution/