( “树” 之 Trie) 208. 实现 Trie (前缀树) ——【Leetcode每日一题】

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

知识点回顾Trie,又称前缀树字典树,用于判断字符串是否存在或者是否具有某种字符串前缀。
( “树” 之 Trie) 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

提示:

  • 1 <= word.length, prefix.length <= 2000
  • wordprefix 仅由小写英文字母组成
  • insertsearchstartsWith 调用次数 总计 不超过 3 ∗ 1 0 4 3 * 10^4 3104

💡思路:使用数组

我们要定义一个名为TrieNode的类,它有两个属性:

  • childs:这是一个大小为26的数组,表示当前节点的子节点。数组的每个元素代表一个字母(从az)。如果当前节点有一个子节点(例如a),则childs数组的相应位置(即索引0)将包含一个TrieNode对象。
  • isLeaf:这是一个布尔值,表示当前节点是否为叶子节点。如果当前节点是叶子节点,则此值为true;否则为false

🍁代码:(Java、C++)

Java

class Trie {
    private class TrieNode{
        TrieNode[] childs = new TrieNode[26];
        boolean isLeaf;
    }

    private TrieNode root = new TrieNode();

    public Trie() {

    }
    
    public void insert(String word) {
        insert(word, root);
    }

    private void insert(String word, TrieNode root){
        if(root == null) return;
        if(word.length() == 0){
            root.isLeaf = true;
            return;
        }
        int index = indexForChar(word.charAt(0));
        if(root.childs[index] == null){
            root.childs[index] = new TrieNode();
        }
        insert(word.substring(1), root.childs[index]);
    }
    private int indexForChar(char c){
        return c - 'a';
    }
    
    public boolean search(String word) {
        return search(word, root);
    }

    private boolean search(String word, TrieNode root){
        if(root == null) return false;
        if(word.length() == 0) return root.isLeaf;
        int index = indexForChar(word.charAt(0));
        return search(word.substring(1), root.childs[index]);
    }
    
    public boolean startsWith(String prefix) {
        return startsWith(prefix, root);
    }

    private boolean startsWith(String prefix, TrieNode root){
        if(root == null) return false;
        if(prefix.length() == 0) return true;
        int index = indexForChar(prefix.charAt(0));
        return startsWith(prefix.substring(1), root.childs[index]);
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

C++

class Trie {
private:
    vector<Trie*> childs;
    bool isLeaf;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->childs[ch] == nullptr) {
                return nullptr;
            }
            node = node->childs[ch];
        }
        return node;
    }

public:
    Trie() : childs(26), isLeaf(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->childs[ch] == nullptr) {
                node->childs[ch] = new Trie();
            }
            node = node->childs[ch];
        }
        node->isLeaf= true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isLeaf;
    }

    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);
 */
🚀 运行结果:

( “树” 之 Trie) 208. 实现 Trie (前缀树) ——【Leetcode每日一题】

🕔 复杂度分析:
  • 时间复杂度:初始化为 O ( 1 ) O(1) O(1),其余操作为 O ( ∣ S ∣ ) O(|S|) O(S),其中 ∣ S ∣ ∣S∣ S 是每次插入或查询的字符串的长度。
  • 空间复杂度 O ( ∣ T ∣ ⋅ Σ ) O(|T|\cdot\Sigma) O(TΣ),其中 ∣ T ∣ |T| T 为所有插入字符串的长度之和, Σ \Sigma Σ 为字符集的大小,本题 Σ = 26 \Sigma=26 Σ=26

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-430096.html

注: 如有不足,欢迎指正!

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

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

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

相关文章

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

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

    2024年02月19日
    浏览(38)
  • LeetCode·每日一题·1177. 构建回文串检测·前缀和

    作者:小迅 链接:https://leetcode.cn/problems/can-make-palindrome-from-substring/solutions/2309940/qian-zhui-he-zhu-shi-chao-ji-xiang-xi-by-n3ps/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。   题意 - 给定一个字符串,选择其中任意位置 L-R,可以重

    2024年02月09日
    浏览(38)
  • 每日一题——LeetCode1455.检查单词是否为句中其他单词的前缀

    方法一 js函数slice()  将字符串按空格符分割为单词数组,记searchWord的长度为n,分割每个单词的前n位看是否和searchWord匹配 消耗时间和内存情况: 方法二 双指针: 来自leetcode官方题解 链接:1455.检查单词是否为句中其他单词的前缀 使用 start 记录单词的起始,end记录单词结尾

    2024年02月19日
    浏览(53)
  • 2023-06-14 LeetCode每日一题(二进制字符串前缀一致的次数)

    点击跳转到题目位置 给你一个长度为 n 、下标从 1 开始的二进制字符串,所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位(即,将 0 变为 1)。 给你一个下标从 1 开始的整数数组 flips ,其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。 二进制字符串 前缀

    2024年02月08日
    浏览(48)
  • 每日一题411数组中两个数的最大异或值(哈希表、前缀树:实现前缀树)

    LeetCode题目:https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/   本题使用哈希表方法主要运用到一个定理:异或满足算法交换律。即如果a^b = c,那么必然 b ^ c = a。且数组中的元素都在 [ 0 , 2 31 ) [0,2^{31}) [ 0 , 2 31 ) ,因此可以确定数值的最高位是30位。   因此,可以假设

    2024年02月05日
    浏览(39)
  • 【每日一题Day208】LC1335工作计划的最低难度 | 动态规划

    工作计划的最低难度【LC1335】 你需要制定一份 d 天的工作计划表。工作之间存在依赖,要想执行第 i 项工作,你必须完成全部 j 项工作( 0 = j i )。 你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和,而一天的工作难度是当天应该完成工作的最大

    2024年02月05日
    浏览(69)
  • 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日
    浏览(38)
  • 实现 Trie (前缀树)

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

    2024年02月10日
    浏览(30)
  • Leetcode每日一题——“用栈实现队列”

    各位CSDN的uu们你们好呀,今天,小雅兰的内容是用栈实现队列,这和小雅兰的上一篇博客“用队列实现栈”好像有点点关系噢,事实上,也确实是这样的,下面,让我们进入Leetcode的世界吧!!! Leetcode每日一题——“用队列实现栈”_认真学习的小雅兰.的博客-CSDN博客    

    2024年02月06日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包