[LeetCode]208. Implement Trie (Prefix Tree)

题目描述

思路

实现字典树的插入、搜索和查找过程 详见代码中的注释

代码

#include <iostream> #include <vector> using namespace std; //定义字典树节点 class TrieNode { public: char content; bool isEnd; int childrenNum; //子节点vector 不止一个子节点 vector<TrieNode*> children; //构造函数 TrieNode() : content(' '), isEnd(false), childrenNum(0) {} TrieNode(char ch) : content(ch), isEnd(false), childrenNum(0) {} //查找字符是否存在子节点中，若存在，则返回节点，不存在返回null TrieNode* findChild(char ch) { if (children.size()) for (auto p : children) if (ch == p->content) return p; return nullptr; } //析构 ~TrieNode() { for (auto child : children) delete child; } }; class Trie { public: //构造函数，初始化根节点 Trie() { root = new TrieNode(); } ~Trie() { delete root; } //插入一个单词 void insert(string word) { //首先查找单词是否存在字典树，若存在直接返回 if (search(word)) return; //初始化当前节点为根节点 TrieNode* cur = root; //遍历单词中的字符 for (char ch : word) { //查找当前节点的子节点中是否含有字符 TrieNode* child = cur->findChild(ch); if (child == nullptr) { //若不存在，新建节点，将节点联入字典树中，并更新当前节点为新建的节点 TrieNode* newNode = new TrieNode(ch); cur->children.push_back(newNode); ++cur->childrenNum; cur = newNode; } else { //若存在，将当前节点更新为子节点 cur = child; } } //将word的最后一个字符设置isend为true，表明根节点到当前节点存储了一个单词 cur->isEnd = true; } bool search(string word) { //初始化当前节点为根节点 TrieNode* cur = root; //遍历查找 for (char ch : word) { TrieNode* node = cur->findChild(ch); //如果字符不存在，返回false if (node == nullptr) return false; //更新当前节点 cur = node; } //检查最后字符的isend，如果不为true，则表明查找到的只是其他单词的前缀 return cur->isEnd == true; } bool startsWith(string prefix) { TrieNode* cur = root; for (char ch : prefix) { TrieNode* node = cur->findChild(ch); if (node == nullptr) return false; cur = node; } return true; } private: TrieNode* root; }; int main() { Trie* trie = new Trie(); trie->insert("test"); cout << "search(test) " << trie->search("test") << endl; cout << "search(tes) " << trie->search("tes") << endl; cout << "startWith(tes) " <<trie->startsWith("tes") << endl; system("pause"); return 0; }