本文共 2436 字,大约阅读时间需要 8 分钟。
题目描述
Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。请你实现 Trie 类:
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。 boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。 boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。示例:
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”] [[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]] 输出 [null, null, true, false, true, null, true]解释
Trie trie = new Trie(); trie.insert(“apple”); trie.search(“apple”); // 返回 True trie.search(“app”); // 返回 False trie.startsWith(“app”); // 返回 True trie.insert(“app”); trie.search(“app”); // 返回 True提示:
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成 insert、search 和 startsWith 调用次数 总计 不超过 3 * 104来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。C++
class Trie { /** Initialize your data structure here. */ vectorchildren; bool isEnd; //表示节点是否是前缀树结尾 Trie* searchPrefix(string prefix){ Trie* node=this; for(char ch:prefix){ ch -= 'a'; if(node->children[ch]==nullptr){ return nullptr; } node=node->children[ch]; } return node; } public: Trie():children(26),isEnd(false){ } /** Inserts a word into the trie. */ void insert(string word){ Trie* node=this; for(char ch:word){ ch -='a'; if(node->children[ch]==nullptr){ node->children[ch]=new Trie(); } node=node->children[ch]; } node->isEnd=true; } /** Returns if the word is in the trie. */ bool search(string word) { Trie* node=this->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) { return this->searchPrefix(prefix) !=nullptr; }};/** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */