大型网站开发价格,广州越秀区儿童医院,网页设计素材免费版,西安企业做网站1--前缀树的实现 前缀树的每一个节点拥有三个成员变量#xff0c;pass表示有多少个字符串经过该节点#xff0c;end表示有多少个字符串以该节点结尾#xff0c;nexts表示该字符串可以走向哪些节点#xff1b; #include iostream
#include unordered_mapstr…1--前缀树的实现 前缀树的每一个节点拥有三个成员变量pass表示有多少个字符串经过该节点end表示有多少个字符串以该节点结尾nexts表示该字符串可以走向哪些节点 #include iostream
#include unordered_mapstruct TreeNode{TreeNode() : pass(0), end(0){}int pass; // 经过次数int end; // 是多少个字符串的结尾std::unordered_mapchar, TreeNode* nexts;
};class Trie{
public:// 构造函数Trie(){root new TreeNode();}void insert(std::string word){if(word.length() 0) return;TreeNode *node root;node-pass;for(int i 0; i word.length(); i){if(node-nexts[word[i]] NULL){ // 哈希表中没有该字符node-nexts[word[i]] new TreeNode(); // 新建该字符}node node-nexts[word[i]];node-pass; // 该字符节点经过的次数}node-end; // 遍历word末尾时节点的end表明以该节点结尾的字符串数}bool search(std::string word){if(word.length() 0) return true;TreeNode *cur root;for(int i 0; i word.length(); i){if(cur-nexts[word[i]] NULL) return 0; // 没有该字符节点cur cur-nexts[word[i]];}return cur-end; // end不为0表明该字符串出现过}bool startWith(std::string prefix){if(prefix.length() 0) return 0;TreeNode *cur root;for(int i 0; i prefix.length(); i){if(cur-nexts[prefix[i]] NULL) return 0; // 前缀没出现过cur cur-nexts[prefix[i]];}return cur-pass; // 有多少个字符串经过该前缀0个表明false;}private:TreeNode *root;
};int main(int argc, char *argv[]){Trie T1;std::string test1 hello;T1.insert(test1);bool res1 T1.search(test1);if(res1) std::cout true std::endl;else std::cout false std::endl;bool res2 T1.startWith(hel);if(res2) std::cout true std::endl;else std::cout false std::endl;return 0;
}
2--LeetCode真题
2-1--实现Trie前缀树 本题不能自定义节点因此将 pass、end 和 nexts 等成员变量转换成类的成员变量新节点就是类的对象 class Trie{
public:// 构造函数Trie(){}void insert(std::string word){if(word.length() 0) return;Trie *node this;node-pass;for(int i 0; i word.length(); i){if(node-nexts[word[i]] NULL){ // 哈希表中没有该字符node-nexts[word[i]] new Trie(); // 新建该字符}node node-nexts[word[i]];node-pass; // 该字符节点经过的次数}node-end; // 遍历word末尾时节点的end表明以该节点结尾的字符串数}bool search(std::string word){if(word.length() 0) return true;Trie *cur this;for(int i 0; i word.length(); i){if(cur-nexts[word[i]] NULL) return 0; // 没有该字符节点cur cur-nexts[word[i]];}return cur-end; // end不为0表明该字符串出现过}bool startsWith(std::string prefix){if(prefix.length() 0) return 0;Trie *cur this;for(int i 0; i prefix.length(); i){if(cur-nexts[prefix[i]] NULL) return 0; // 前缀没出现过cur cur-nexts[prefix[i]];}return cur-pass; // 有多少个字符串经过该前缀0个表明false;}private:int pass 0; // 经过次数int end 0; // 是多少个字符串的结尾std::unordered_mapchar, Trie* nexts;
};
