首页 > 其他分享 >字典树

字典树

时间:2023-02-19 11:56:26浏览次数:49  
标签:ch word Trie nownode children 字典

一、概念

字典树(Trie)用于判断字符串是否存在或者是否具有某种字符串前缀。

 

包含三个单词 "sea","sells","she" 的 Trie 长这样:

 

 

 

为什么需要用字典树解决这类问题呢?假如我们有一个储存了近万个单词的字典,即使我们
使用哈希,在其中搜索一个单词的实际开销也是非常大的,且无法轻易支持搜索单词前缀。然而
由于一个英文单词的长度n 通常在10 以内,如果我们使用字典树,则可以在O(n)——近似O(1)
的时间内完成搜索,且额外开销非常小。

 

二、题解 

lc 208. 实现 Trie (前缀树)

 

class Trie {
private:
    vector<Trie*> children;  
    bool isEnd;  // 标记该节点是否是单词的最后一个字母

public:
    // 每个节点都含26个指向Trie的指针
    Trie(): children(26), isEnd(false) {}
    
    void insert(string word) {
        Trie* nownode = this;  // this表示当前Trie对象的地址(Trie* obj = new Trie();)
        for (char ch: word) {
            ch -= 'a';
            if (nownode->children[ch] == nullptr) {
                nownode->children[ch] = new Trie();  
            }
            nownode = nownode->children[ch];
        }
        nownode->isEnd = true;  // 最后一个字母设为true
    }
    
    bool search(string word) {
        Trie* nownode = this;
        for (char ch: word) {
            ch -= 'a';
            if (nownode->children[ch] == nullptr) {
                return false;
            }
            nownode = nownode->children[ch];
        }
        return nownode->isEnd;  // 若nownode->isEnd = false, 则表明字典树中并无该单词,(未到结尾)
    }
    
    bool startsWith(string prefix) {
        Trie* nownode = this;
         for (char ch: prefix) {
            ch -= 'a';
            if (nownode->children[ch] == nullptr) {
                return false;
            }
            nownode = nownode->children[ch];
        }
        return true; 
    }
};

/**
 * 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);
 */

  

 

参考视频:

https://leetcode.cn/problems/implement-trie-prefix-tree/solution/gua-he-xin-shou-peng-you-de-shi-pin-ti-j-fhvw/

标签:ch,word,Trie,nownode,children,字典
From: https://www.cnblogs.com/spacerunnerZ/p/17132384.html

相关文章

  • 关于python中将字典的所有key组成一个列表的方式
    关于python的字典,我们可以通过MyDict.keys()得到这个字典的所有的key,然后还能通过for循环进行遍历但是细心一点、我们可以发现,MyDict.keys()其实是一个<class'dict_ke......
  • python学习笔记四:字典
    字典和集合一样是无序的,不能通过索引来存取,只能通过键来存取。字典的键必须是不可变的数据类型,如数字,字符串,元组等,列表等可变对象不能作为键。不允许同一个键出现两次,创建......
  • python(13)--字典(Dict)
     一、字典的基本操作1.定义字典 字典也是一个列表型的数据结构,字典的数据是用“{}”装的(列表:[],元组:()),字典的元素是一一对应的关系“key-value”。格式:Dictname={key1:......
  • 扩展字典的类
    classValueDict(dict):def__init__(self,*args,**kargs):super().__init__(*args,**kargs)defgetValueByKey(self,val):result=[]......
  • 前端字典字段处理enum.js
    enum.js/***获取枚举值:STATUSMAP.TTT*获取枚举描述:STATUSMAP.getDesc('SH')*通过枚举值获取描述:STATUSMAP.getDescFromValue('TG')*/functioncreateEnum(def......
  • totaoBrought()读取嵌套字典列表内容
    allGuests={'Alice':{'apples':5,'pretzels':12},'Bob':{'hamsandwiches':3,'apples':2},'Carol':{'cups':3,'applepies':1}}deftotal(x,y)......
  • 数据字典标准与统一的重要性(码表&枚举值)
    在日常的软件开发当中,开发者经常会听到“公共代码、编码、码表、枚举值”这样的名词,对这些概念可能会有些混淆和认知不透彻,那么这篇文章会详细论述一下关于数据字典的相关概......
  • 字典树模板
    字典树数组模拟版: #include<cstdio>#include<algorithm>#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1000010;consti......
  • Dumb feature Gym - 102020D 【 字典树 】
    D-Dumbfeature Gym-102020D  &:字典树的模板题,根据来的串建树,再查询。不过当时没弄出来,要映射一下子,把字母映射成键盘上的数字。ps:这题的数据应该是有问题,只......
  • TreeMap是按照key的字典顺序来排序
    一、TreeMapTreeMap默认排序规则:按照key的字典顺序来排序(升序)字典排序(lexicographicalorder)是一种对于随机变量形成序列的排序方法。即按照字母顺序,或者数字小大顺序,由小......