C++实现trid
class TrieNode{ public: TrieNode():End(false), R(26){ links.resize(R); } void setEnd(){ End = true; } bool isEnd(){ return End; } bool containsKey(char key){ return links[key - 'a'] != nullptr; } void put(char key, TrieNode* node){ links[key - 'a'] = node; } TrieNode* get(char key){ return links[key - 'a']; } private: vector<TrieNode*> links; bool End; int R; }; class Trie { public: /** Initialize your data structure here. */ TrieNode* root; Trie(){ root = new TrieNode(); } /** Inserts a word into the trie. */ void insert(string word) { TrieNode* p = root; for(int i = 0; i < word.size(); ++i) { if(!p->containsKey(word[i])) { p->put(word[i], new TrieNode()); } p = p->get(word[i]); } p->setEnd(); } TrieNode* searchPrefix(string word) { TrieNode* p = root; for(int i = 0; i < word.size(); ++i) { if (p->containsKey(word[i])) { p = p->get(word[i]); } else { return nullptr; } } return p; } /** Returns if the word is in the trie. */ bool search(string word) { TrieNode* node = searchPrefix(word); return node != nullptr && node->isEnd(); } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { TrieNode* node = searchPrefix(prefix); return node != nullptr; } };
原文链接: https://www.cnblogs.com/qiang-wei/p/12287114.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/328259
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!