金坛区建设工程质量监督网站,深圳今天新增确诊名单,网站+做内容分发资格,招聘seo专员[TOC](LeetCode 热题 100_实现 Trie (前缀树)#xff08;54_208#xff09;)
题目描述#xff1a;
Trie#xff08;发音类似 “try”#xff09;或者说 前缀树 是一种树形数据结构#xff0c;用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景[TOC](LeetCode 热题 100_实现 Trie (前缀树)54_208)
题目描述
Trie发音类似 “try”或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补全和拼写检查。
请你实现 Trie 类
Trie() 初始化前缀树对象。 void insert(String word) 向前缀树中插入字符串 word 。 boolean search(String word) 如果字符串 word 在前缀树中返回 true即在检索之前已经插入否则返回 false 。 boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix 返回 true 否则返回 false 。
输入输出样例
示例 1 输入 [“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 次
题解
解题思路
思路一前缀树字典树
1、解决此问题我们需要了解什么是前缀树了解其树形结构和特性。 例 从上图中我们可以分析出前缀树的一些特性
① 树形结构每个节点代表一个字符根节点代表空字符串。每一条从根节点到叶子节点的路径代表一个字符串。 ②共享前缀所有具有相同前缀的字符串会共享相同的路径从根节点到某个节点的路径是相同的。因此前缀树适合存储一组具有相同前缀的字符串。 ③快速查找通过字符逐一比对的方式可以在树中快速找到一个完整的字符串或前缀。 ④插入和查找效率前缀树的查找、插入时间复杂度都为 O(L)其中 L 是字符串的长度。由于它基于字符逐层匹配因此比起常规的哈希表等数据结构在某些场景下效率更高尤其是当需要进行前缀匹配或字典树操作时。
2、具体思路如下 通过1中的例题可得 ① Trie() {} 需要我们根据问题的特性进行树形结构的创建每个节点代表一个字符因 a~z 是26个字符所以我们需要每个节点含有26个指向下一个结点的指针。还需使用一个标志变量来存储当前字母是否是单词的最后一个字母。 ② 插入单词到前缀树 insert进行字母插入时若之前插入过当前字母则跳过否则将创建节点。若当前字母是单词的最后一个字母则进行标记。 ③ 查找单词是否在前缀树中存在 search进行逐个字母的判断若当前字母不在前缀树中则返回false。若单词中的字母都存在前缀树中还需判断单词的最后一个字母在前缀树中是否被标记若已标记则返回true否则返回false。 ④ 检查是否有单词以给定的前缀开始 startsWith 只需逐个字母进行判断若当前字母不在前缀树中则返回false。若逐个判断匹配成功则返回true无需进行单词末尾标记判断
3、复杂度分析 ① 时间复杂度初始化为 O(1)其余操作为 O(∣S∣)其中 ∣S∣ 是每次插入或查询的字符串的长度。插入需逐个字母插入查询需逐个字母进行判断。 ② 空间复杂度O(∣T∣⋅Σ)其中 ∣T∣ 为所有插入字符串的长度之和Σ 为字符集的大小本题 Σ26。
代码实现
代码实现思路一前缀树字典树
class Trie {
private://子节点的指针数组大小为26代表字母a-zvectorTrie * children;//标记当前节点是否是一个单词的结尾bool isEnd;// 辅助函数查找给定前缀路径的最后一个节点Trie* searchPerfix(string prefix){// 从根节点开始Trie* node this;for (char ch : prefix){// 将字符转换为0到25的索引a0, b1, ..., z25ch-a; // 如果该子节点不存在返回空表示前缀不存在if (node-children[ch] nullptr) return nullptr;// 移动到下一个节点nodenode-children[ch]; }// 返回最后的节点表示前缀存在return node;}public:// 构造函数初始化一个空的Trie树Trie() : children(26),isEnd(false) {}// 插入一个单词到Trie树中void insert(string word) {// 从根节点开始Trie* nodethis;for (char ch : word){// 将字符转换为0到25的索引ch -a; // 如果该子节点不存在, 创建一个新节点if (node-children[ch]nullptr){node-children[ch]new Trie();}//移动到下一个节点nodenode-children[ch];}// 设置单词的结尾node-isEndtrue;}// 查找单词是否存在于Trie树中bool search(string word) {//查找单词的路径Trie *nodethis-searchPerfix(word); // 如果找到路径且是单词结尾返回truereturn node !nullptr node-isEnd;}// 检查是否存在以给定前缀开头的单词(如果前缀存在返回true)bool startsWith(string prefix) {return this-searchPerfix(prefix)!nullptr;}
};以思路一为例进行调试
#includeiostream
#includevector
using namespace std;class Trie {
private://子节点的指针数组大小为26代表字母a-zvectorTrie * children;//标记当前节点是否是一个单词的结尾bool isEnd;// 辅助函数查找给定前缀路径的最后一个节点Trie* searchPerfix(string prefix){// 从根节点开始Trie* node this;for (char ch : prefix){// 将字符转换为0到25的索引a0, b1, ..., z25ch-a; // 如果该子节点不存在返回空表示前缀不存在if (node-children[ch] nullptr) return nullptr;// 移动到下一个节点nodenode-children[ch]; }// 返回最后的节点表示前缀存在return node;}public:// 构造函数初始化一个空的Trie树Trie() : children(26),isEnd(false) {}// 插入一个单词到Trie树中void insert(string word) {// 从根节点开始Trie* nodethis;for (char ch : word){// 将字符转换为0到25的索引ch -a; // 如果该子节点不存在, 创建一个新节点if (node-children[ch]nullptr){node-children[ch]new Trie();}//移动到下一个节点nodenode-children[ch];}// 设置单词的结尾node-isEndtrue;}// 查找单词是否存在于Trie树中bool search(string word) {//查找单词的路径Trie *nodethis-searchPerfix(word); // 如果找到路径且是单词结尾返回truereturn node !nullptr node-isEnd;}// 检查是否存在以给定前缀开头的单词(如果前缀存在返回true)bool startsWith(string prefix) {return this-searchPerfix(prefix)!nullptr;}
};int main(int argc, char const *argv[])
{// 创建一个新的 Trie 对象Trie trie; // 插入单词 appletrie.insert(apple); // 查找单词apple是否存在返回 Truecouttrie.search(apple)endl; // 查找单词apple是否存在返回 Falsecouttrie.search(app)endl; // 查找当前存储的单词中是否存在前缀app返回 Truecouttrie.startsWith(app)endl; // 插入单词 apptrie.insert(app); couttrie.search(app)endl; //查找单词app是否存在返回 Truereturn 0;
}LeetCode 热题 100_实现 Trie (前缀树)54_208)原题链接 欢迎大家和我沟通交流(✿◠‿◠)
