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);
*/