https://leetcode.com/problems/stream-of-characters/description/
题目解析
题目的意思就是通过不断的query(c)
来添加历史记录,然后看是不是历史记录里包括给定的词。
方法
解法关键在于如何快速的找到这些词,这里使用前缀树来使每次查找的时间复杂度在O(logW), W是最长的单词,题目里W最大是200,最多查询40000次,故不会超时
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| class StreamChecker { public: struct TreeNode { TreeNode *left; TreeNode *right; TreeNode *letters[26]; bool is_word = false; }; StreamChecker(vector<string> &words) { trie = new TreeNode(); for (auto &word : words) { reverse(word.begin(), word.end()); build(trie, word); } }
bool query(char letter) { history.push_back(letter); return search(trie, history.size() - 1); }
void build(TreeNode *root, string &word) { for (int i = 0; i < word.size(); i++) { if (!root->letters[word[i] - 'a']) { root->letters[word[i] - 'a'] = new TreeNode(); } if (i == word.size() - 1) { root->letters[word[i] - 'a']->is_word = true; } root = root->letters[word[i] - 'a']; } }
bool search(TreeNode *trie, int index) { for (int i = history.size() - 1; i >= 0; i--) { char c = history[i]; TreeNode *next = trie->letters[c - 'a']; if (!next) { return false; } else if (next->is_word) { return true; } trie = next; } return false; }
private: vector<char> history; TreeNode *trie; };
|