leetcode做题笔记208. 实现 Trie (前缀树)

这篇具有很好参考价值的文章主要介绍了leetcode做题笔记208. 实现 Trie (前缀树)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

思路一:前缀树

c++解法

class Trie {
private:
     bool isEnd;
        Trie* next[26];

public:
  
    Trie() {
         isEnd = false;
        memset(next, 0, sizeof(next));
    }
    
    void insert(string word) {
        Trie* node = this;
        for(char c:word){
            if(node->next[c-'a']==NULL)node->next[c-'a']=new Trie();
            node = node->next[c-'a'];
        }
        node->isEnd = true;


    }
    
    bool search(string word) {
    Trie* node = this;
    for (char c : word) {
        node = node->next[c - 'a'];
        if (node == NULL) {
            return false;
        }
    }
    return node->isEnd;
}

    bool startsWith(string prefix) {
    Trie* node = this;
    for (char c : prefix) {
        node = node->next[c-'a'];
        if (node == NULL) {
            return false;
        }
    }
    return true;
}

};

分析:

本题要实现前缀树这种数据结构,本题解参照精选题解中思路,采用节点记录每个字符,分叉出多节点实现前缀树,此处采用isEnd这个bool类型判断是否到达终点,来完成search函数的判断但其实可以优化掉此数据,留给读者自己思考

总结:

本题考察对前缀树这种数据结构的实现,并需完成几个关于前缀树的方法,利用二叉树相关知识可以解答,前缀树同时也是一种二叉树的延申,可以利用前缀树完成许多相关题目文章来源地址https://www.toymoban.com/news/detail-734518.html

到了这里,关于leetcode做题笔记208. 实现 Trie (前缀树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode、208. 实现 Trie (前缀树)【中等,自定义数据结构】

    博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。 博主所有博客文件目录索引:博客目录索引(持续更新) 视频平台:

    2024年02月19日
    浏览(41)
  • Grind75第13天 | 208.实现Trie、54.螺旋矩阵、721.账户合并

    题目链接:https://leetcode.com/problems/implement-trie-prefix-tree 解法: 这个题非常经典,背下来。 首先需要自己实现Node的类,属性为children和是否为单词的标记,再去初始化Trie的类。 在插入和查询的过程中,都要不断让指针指向children。 参考题解:实现Trie 边界条件:无 题目链接:

    2024年01月20日
    浏览(44)
  • 力扣208题:实现Tire(前缀树)

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 设计一个前缀节点类,这个类保存了,当前字符所在层级,是否为某个词的词尾,以及后续所有字符的节点,采用HashMap存储,key是后续字符,value就是下一个节点对象; 1 字符所在层级level变量的设计:因为词的匹配不光要

    2024年01月21日
    浏览(43)
  • 实现 Trie (前缀树)

    实现 Trie (前缀树) word 和 prefix 仅由小写英文字母组成 首先要理解前缀树是什么,参照该篇文章【图解算法】模板+变式——带你彻底搞懂字典树(Trie树) 在了解前缀树是什么后,设计前缀树就会更加容易,因为本题中所有单词都仅由小写英文字母组成,所以哈希表只需要26个空

    2024年02月10日
    浏览(31)
  • 54、图论-实现Trie前缀树

    主要是构建一个trie前缀树结构。如果构建呢?看题意,应该当前节点对象下有几个属性: 1、next节点数组 2、是否为结尾 3、当前值 代码如下:

    2024年04月26日
    浏览(40)
  • 算法第十八天-实现Trie(前缀树)

    本文是前缀入门教程 从二叉树说起 前缀树,也是一种树。为了理解前缀树,我们先从二叉树说起。常见的二叉树结构是下面这样子的: 可以看到一个树的节点包含了三个元素:该节点本身的值,左子树的指针,右子树的指针。二叉树可视化是下面这样子的: 二叉树的每个节

    2024年01月18日
    浏览(34)
  • leetcode做题笔记58

    给你一个字符串  s ,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中  最后一个  单词的长度。 单词  是指仅由字母组成、不包含任何空格字符的最大子字符串。 本题要求最后一个单词长度,只需从后向前遍历,ans不断增加,一旦遇到空格则输出ans的值 本

    2024年02月14日
    浏览(44)
  • leetcode做题笔记45

    给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处: 0 = j = nums[i]  i + j n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

    2024年02月15日
    浏览(55)
  • leetcode做题笔记41

    给你一个未排序的整数数组  nums  ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为  O(n)  并且只使用常数级别额外空间的解决方案。 目录 思路一:利用负数进行区分 分析: 思路二:交换法 分析: 总结: 时间复杂度O(n),空间复杂度O(1) 本题一开始想到

    2024年02月16日
    浏览(36)
  • leetcode做题笔记69

    给你一个非负整数  x  ,计算并返回  x  的  算术平方根  。 由于返回类型是整数,结果只保留  整数部分  ,小数部分将被  舍去 。 注意: 不允许使用任何内置指数函数和算符,例如  pow(x, 0.5)  或者  x ** 0.5  。 由于本题是求平方根,可直接看中位数的平方是否大于

    2024年02月13日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包