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日
    浏览(38)
  • Grind75第13天 | 208.实现Trie、54.螺旋矩阵、721.账户合并

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

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

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

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

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

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

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

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

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

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

    给你一个字符串  path  ,表示指向某一文件或目录的 Unix 风格  绝对路径  (以  \\\'/\\\'  开头),请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中,一个点( . )表示当前目录本身;此外,两个点 ( .. ) 表示将目录切换到上一级(指向父目录);两者都可以

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

    给你两个单词  word1  和  word2 ,  请返回将  word1  转换成  word2  所使用的最少操作数   。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 时间复杂度O(n^2),空间复杂度O(n) 本题将一个字符串变为另一个字符串,首先长度需变为一致,即

    2024年02月13日
    浏览(39)
  • leetcode做题笔记53

    给你一个整数数组  nums  ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组  是数组中的一个连续部分。 时间复杂度O(n),空间复杂度O(1) 本题要求最大子数组和,可考虑先求出每个元素的前缀和,再判断是否前缀和加现元素是否

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

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

    2024年02月13日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包