本文主要是介绍Leetcode171: Implement Trie (Prefix Tree)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Implement a trie with insert, search, and startsWith methods.
Trie树又被称为字典树、前缀树，是一种用于快速检索的多叉树。Tried树可以利用字符串的公共前缀来节省存储空间。
但如果系统存在大量没有公共前缀的字符串，相应的Trie树将非常消耗内存。
Trie树的基本性质如下：
- 根节点不包括字符，除根节点外每个节点包括一个支付。
- 从根节点到某一节点，路径上经过的字符连接起来，即为对应的字符串。
- 每个节点的所有子节点包含的字符串各不相同。
本题中的Trie树可以简单实现如下：
Trie树节点数据结构定义如下：
- val表示该节点对应的字符
- 子节点简单用一个数组表示，这样实现比较简单，但比较耗费内存
- isWord标记从根节点到该节点是否表示一个单词，还是另一单词的前缀。
class TrieNode {
public:// Initialize your data structure here.char var; bool isWord; TrieNode* children[26]; // Initialize your data structure here. TrieNode() { var = 0; isWord = false; memset(children, 0x0, sizeof(TreeNode*)*26); } TrieNode(char c){ var = c; isWord = false; memset(children, 0x0, sizeof(TreeNode*)*26); }
};class Trie {
public:Trie() {root = new TrieNode();}// Inserts a word into the trie.void insert(string word) {TrieNode* pNode = root; if (word.length() <= 0) { return; } for (int i= 0; i<word.length(); i++) { char c= word[i]; if (pNode->children[c-'a'] == 0) { TrieNode *pNew = new TrieNode(c); pNode->children[c-'a'] = pNew; } pNode = pNode->children[c-'a']; } pNode->isWord = true;}// Returns if the word is in the trie.bool search(string word) {TrieNode *pNode = root; if (word.length() <= 0) return true; for (int i =0; i<word.length(); i++) { char c = word[i]; pNode = pNode->children[c-'a']; if (pNode == NULL) return false; } return pNode->isWord; }// Returns if there is any word in the trie// that starts with the given prefix.bool startsWith(string prefix) {TrieNode *pNode = root; if (prefix.length()<=0) return true; for (int i=0; i<prefix.length(); i++) { char c = prefix[i]; pNode = pNode->children[c-'a']; if (pNode == NULL) return false; } return true; }private:TrieNode* root;
};// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");这篇关于Leetcode171: Implement Trie (Prefix Tree)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
