LeetCode 1032: Stream of Characters

Question

I'm posting my code for a LeetCode problem copied here. If you have time and would like to review, please do so. Thank you!

Problem

Implement the StreamChecker class as follows:

• StreamChecker(words): Constructor, init the data structure with the given words.
• query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

Example:

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
streamChecker.query('a');          // return false
streamChecker.query('b');          // return false
streamChecker.query('c');          // return false
streamChecker.query('d');          // return true, because 'cd' is in the wordlist
streamChecker.query('e');          // return false
streamChecker.query('f');          // return true, because 'f' is in the wordlist
streamChecker.query('g');          // return false
streamChecker.query('h');          // return false
streamChecker.query('i');          // return false
streamChecker.query('j');          // return false
streamChecker.query('k');          // return false
streamChecker.query('l');          // return true, because 'kl' is in the wordlist

Note:

• \$1 \le \text{words.length} \le 2000\$
• \$1 \le \text{words[i].length} \le 2000\$
• Words will only consist of lowercase English letters.
• Queries will only consist of lowercase English letters.
• The number of queries is at most 40000.

Code

#include <unordered_map>
#include <string>
#include <algorithm>

class Trie {
    std::unordered_map<char, Trie*> alphabet_map;
    bool is_word;

public:
    Trie() {
        is_word = false;
    }

    // Inserts in the trie
    void insert(const std::string word) {
        if (word.length() == 0) {
            return;
        }

        Trie* temp_trie = this;

        for (auto letter : word) {
            if (temp_trie->alphabet_map.find(letter) != temp_trie->alphabet_map.end()) {
                temp_trie = temp_trie->alphabet_map[letter];

            } else {
                temp_trie->alphabet_map[letter] = new Trie();
                temp_trie = temp_trie->alphabet_map[letter];
            }
        }

        temp_trie->is_word = true;
    }

    // Searches the word in the trie
    bool search(const std::string word) {
        if (word.length() == 0) {
            return false;
        }

        Trie* temp_trie = this;

        for (auto letter : word) {
            if (temp_trie->alphabet_map.find(letter) == temp_trie->alphabet_map.end()) {
                return false;
            }

            temp_trie = temp_trie->alphabet_map[letter];

            if (temp_trie->is_word) {
                return true;
            }
        }

        return temp_trie->is_word;
    }
};

class StreamChecker {
    Trie trie_stream;
    std::string string_stream = "";
    int word_length = 0;

public:
    StreamChecker(const std::vector<std::string>& words) {
        for (auto word : words) {
            std::reverse(word.begin(), word.end());
            word_length = std::max(word_length, (int) word.length());
            trie_stream.insert(word);
        }
    }


    bool query(const char letter) {
        string_stream = letter + string_stream;

        if (string_stream.length() > word_length) {
            string_stream.pop_back();
        }

        return trie_stream.search(string_stream);
    }
};

Reference

LeetCode has a template for answering questions. There is usually a class named Solution with one or more public functions which we are not allowed to rename. For this question, the template is:

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        
    }
    
    bool query(char letter) {
        
    }
};

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

• Problem

• Discuss

• Trie

Answer 1

Template

You can't rename functions; but can you change their signature? i.e.

StreamChecker(vector<string>& words) {

would be better as

StreamChecker(const vector<string> &words) {

Similarly,

void insert(const std::string word) {

should be

void insert(const std::string &word) {

The same for search.

Also, the const in

bool query(const char letter) {

isn't as important, since letter is itself an immutable letter. It would be more important if this were a reference or pointer.

Finally, your search method does not modify members, so:

bool search(const std::string &word) const {

Answer 2

In addition to what Reinderien said:

Move class Trie inside class StreamChecker

Your class Trie is not a generic class, but rather a specialized trie implementation specifically for StreamChecker. You can move it inside class StreamChecker, so that it is clear that they belong to each other, and so that class Trie does not pollute the global namespace:

class StreamChecker {
    class Trie {
        ...
    };

    Trie trie_stream;
    ...
};

Store Tries by value

Your class Trie has a memory leak: it calls new Trie(), but there is no corresponding delete in sight. You could write a destructor that iterates over alphabet_map and calls delete on the values, or even use std::unique_ptr to track ownership of the memory, but there is no need for this at all. After all, std::map already takes care of managing the memory necessary to store the keys and values. So remove that pointer and write:

class Trie {
    std::unordered_map<char, Trie> alphabet_map;
    ...
    void insert(const std::string &word) {
        if (word.empty()) {
            return;
        }

        Trie *temp_trie = this;

        for (auto letter: word) {
             temp_trie = &temp_trie->alphabet_map[letter];
        }

        temp_trie->is_word = true;
    }
};

Note that in search() you need to do similar modifications, but there you do need to explicitly check whether the letter is present in the alphabet_map.