字典树。
测试中有：aaaaaaaaaaa… 的输入，，如果每个节点用定长数组存储孩子的话，那就是26^len的空间复杂度（len为输入的长度），内存会不够的。
所以用map<char, TrieNode*>保存其孩子。
代码：
#include <string>#include <vector>#include <map>using namespace std;class TrieNode{public:// Initialize your data structure here.TrieNode(){is_word = false;}void insert(const string& word){if (!word.empty()){nodes[word.front()] =nodes[word.front()] != nullptr ?nodes[word.front()] : new TrieNode();nodes[word.front()]->insert(word.substr(1));} else{is_word = true;}}bool search(string word){if (!word.empty()){if (nodes[word.front()] == nullptr){return false;} else{return nodes[word.front()]->search(word.substr(1));}}return is_word;}bool startsWith(string prefix){if (!prefix.empty()){if (nodes[prefix.front()] == nullptr){return false;} else{return nodes[prefix.front()]->startsWith(prefix.substr(1));}}return true;}// MLE!!!// TrieNode* nodes[26];map<char, TrieNode*> nodes;bool is_word;};class Trie{public:Trie(){root = new TrieNode();}// Inserts a word into the trie.void insert(string word){root->insert(word);}// Returns if the word is in the trie.bool search(string word){return root->search(word);}// Returns if there is any word in the trie// that starts with the given prefix.bool startsWith(string prefix){return root->startsWith(prefix);}private:TrieNode* root;};
版权声明：本文为博主原创文章，未经博主允许不得转载。
爱的力量大到可以使人忘记一切，却又小到连一粒嫉妒的沙石也不能容纳
