算法:字典树 (转自九章算法)

这篇具有很好参考价值的文章主要介绍了算法:字典树 (转自九章算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 

 

https://www.jiuzhang.com/solution/implement-trie/

算法:字典树

思路:

  • 题目要求实现一个Trie,包含插入、查找和查找前缀三个方法。
  • Trie树也称字典树,因为其效率很高,所以在在字符串查找、前缀匹配等中应用很广泛,其高效率是以空间为代价的。
  • 原理:利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低查询操作的复杂度。
  • 定义结点Node里包含一个isWord(表示这个结点是否是一个单词的结尾)和一个大小为26的next。

1.定义一个根结点root作为整棵树的查找起点。

2.比如插入一个单词apple:

我们从root开始,依次往下查找a,p,p,l,e:如果在结点n的下一个字母里没有找到我们想要的字母ch,我们就增加新结点到结点n的next[],式子next[ch-'a']=new Node()。

3.查找一个单词app:

我们从root开始,依次往下查找a,p,p:如果在结点n的下一个字母里没有找到我们想要的字母ch,那么说明不存在,返回False;如果有,那么继续往下找,直到查找的单词app找到最后一位,这时候我们判断一下这个位置的isWord是否为True,如果为True说明这是一个完整单词,否则只是部分,返回False。

4.查找一个前缀

查找一个前缀和查找一个单词的区别就是,当我们想要查找的前缀找到最后一位,不需要判断是否是完整的单词,直接返回True即可。如果不能全部找到则返回False。

复杂度

  • 空间复杂度:字典树每个节点都需要用一个大小为26的数组来存储子节点的指针,所以空间复杂度较高。
  • 时间复杂度:假设所有插入字符串长度之和为n,构建字典树的时间复杂度为O(n);假设要查找的所有字符串长度之和为k,查找的时间复杂度为O(k)。因此时间复杂度为O(n+k)
java
c++
python
 
 
 
public class Trie {
    private class Node{
        // isWord表示这个结点是否为一个单词的结尾
        // next[]表示这个结点的下一个26个字母结点
        public boolean isWord;  
        public Node[] next; 
        
        public Node() {
            this.isWord = false;
            this.next = new Node[26];
        }
    }
    
    private Node root;
    
    public Trie() {
        root = new Node(); 
    }

    /*
     * @param word: a word
     * @return: nothing
     */
    public void insert(String word) {
        Node now = root;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            // 依次寻找每个字符
            // 如果所有下一个结点中没有当前字符,则增加新结点到下一个next[pos]
            int pos = word.charAt(i) - 'a';
            if (now.next[pos] == null) {
                now.next[pos] = new Node();
            }
            now = now.next[pos];
        }
        now.isWord = true;
    }

    /*
     * @param word: A string
     * @return: if the word is in the trie.
     */
    public boolean search(String word) {
        // 查找单词
        int n = word.length();
        Node now = root;
        for (int i = 0; i < n; i++) {
            int ch = word.charAt(i) - 'a';
            // 如果有下一个对应字符的结点,那么继续查找下一个结点
            // 如果没有下一个对应字符的结点,那么说明查找单词失败
            if (now.next[ch] != null) {
                now = now.next[ch];
            }
            else {
                return false;
            }
        }
        // 如果每个字符都有且是完整单词,才说明查找单词成功
        return now.isWord;
    }

    /*
     * @param prefix: A string
     * @return: if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        // 查找前缀
        int n = prefix.length();
        Node now = root;
        for (int i = 0; i < n; i++) {
            int ch = prefix.charAt(i) - 'a';
            // 如果有下一个对应字符的结点,那么继续查找下一个结点
            // 如果没有下一个对应字符的结点,那么说明查找前缀失败
            if (now.next[ch] != null) {
                now = now.next[ch];
            }
            else {
                return false;
            }
        }
        return true;
    }
}
 
 
 
 
赞同
2
 
令狐冲精选
更新于 6/9/2021, 6:57:33 PM
cpp

Trie(前缀树) 的模板应用.

维基百科: https://zh.wikipedia.org/zh-hans/Trie文章来源地址https://www.toymoban.com/news/detail-710031.html

class TrieNode {
public:
    // Initialize your data structure here.
    TrieNode() {
        for (int i = 0; i < 26; i++)
            next[i] = NULL;
        isString = false;
    }
    TrieNode *next[26];
    bool isString;
};
 
class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
 
    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode *p = root;
        for (int i = 0; i < word.size(); i++) {
            if (p->next[word[i]-'a'] == NULL) {
                p->next[word[i]-'a'] = new TrieNode();
            }
            p = p->next[word[i]-'a'];
        }
        p->isString = true;
    }
 
    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode *p = root;
        for (int i = 0; i < word.size(); i++) {
            if (p == NULL) return false;
            p = p->next[word[i]-'a'];
        }
        if (p == NULL || p->isString == false) 
            return false;
        return true;
         
    }
 
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *p = root;
        for (int i = 0; i < prefix.size(); i++) {
            p = p->next[prefix[i]-'a'];
            if (p == NULL) return false;
        }
        return true;
    }
 
private:
    TrieNode* root;
};
赞同
1
 
令狐冲精选
更新于 6/9/2020, 4:03:58 AM
java

Trie(前缀树) 的模板应用.

维基百科: https://zh.wikipedia.org/zh-hans/Trie

// Version 1: Array of TrieNode
class TrieNode {
    private TrieNode[] children;
    public boolean hasWord;
    
    public TrieNode() {
        children = new TrieNode[26];
        hasWord = false;
    }
    
    public void insert(String word, int index) {
        if (index == word.length()) {
            this.hasWord = true;
            return;
        }
        
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            children[pos] = new TrieNode();
        }
        children[pos].insert(word, index + 1);
    }
    
    public TrieNode find(String word, int index) {
        if (index == word.length()) {
            return this;
        }
        
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            return null;
        }
        return children[pos].find(word, index + 1);
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        root.insert(word, 0);
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = root.find(word, 0);
        return (node != null && node.hasWord);
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = root.find(prefix, 0);
        return node != null;
    }
}

// Version 2: HashMap Version, this version will be TLE when you submit on LintCode
class TrieNode {
    // Initialize your data structure here.
    char c;
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    boolean hasWord;
    
    public TrieNode(){
        
    }
    
    public TrieNode(char c){
        this.c = c;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode cur = root;
        HashMap<Character, TrieNode> curChildren = root.children;
        char[] wordArray = word.toCharArray();
        for(int i = 0; i < wordArray.length; i++){
            char wc = wordArray[i];
            if(curChildren.containsKey(wc)){
                cur = curChildren.get(wc);
            } else {
                TrieNode newNode = new TrieNode(wc);
                curChildren.put(wc, newNode);
                cur = newNode;
            }
            curChildren = cur.children;
            if(i == wordArray.length - 1){
                cur.hasWord= true;
            }
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if(searchWordNodePos(word) == null){
            return false;
        } else if(searchWordNodePos(word).hasWord) 
          return true;
          else return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if(searchWordNodePos(prefix) == null){
            return false;
        } else return true;
    }
    
    public TrieNode searchWordNodePos(String s){
        HashMap<Character, TrieNode> children = root.children;
        TrieNode cur = null;
        char[] sArray = s.toCharArray();
        for(int i = 0; i < sArray.length; i++){
            char c = sArray[i];
            if(children.containsKey(c)){
                cur = children.get(c);
                children = cur.children;
            } else{
                return null;
            }
        }
        return cur;
    }
}
赞同
1
 
令狐冲精选
更新于 6/9/2020, 4:03:58 AM
python3

代码兼容Python 2 & 3 新建一个 TrieNode 的 class 用于表示 Trie 中的节点,包含 children 和 is_word 两个属性

Trie(前缀树) 的模板应用.

维基百科: https://zh.wikipedia.org/zh-hans/Trie

class TrieNode:
    
    def __init__(self):
        self.children = {}
        self.is_word = False
    
    
class Trie:
    
    def __init__(self):
        self.root = TrieNode()

    """
    @param: word: a word
    @return: nothing
    """
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        
        node.is_word = True

    """
    return the node in the trie if exists 
    """
    def find(self, word):
        node = self.root
        for c in word:
            node = node.children.get(c)
            if node is None:
                return None
        return node
        
    """
    @param: word: A string
    @return: if the word is in the trie.
    """
    def search(self, word):
        node = self.find(word)
        return node is not None and node.is_word

    """
    @param: prefix: A string
    @return: if there is any word in the trie that starts with the given prefix.
    """
    def startsWith(self, prefix):
        return self.find(prefix) is not None
赞同
1
 

到了这里,关于算法:字典树 (转自九章算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • nginx将xxx.com重定向到www.xxx.com配置

    有时候,我们网站,需要将顶级域名xxx.com统一跳转到二级域名www.xxx.com下。这时候,我们可以通过修改nginx配置达到我们的目的。

    2024年03月23日
    浏览(56)
  • Docker未授权访问漏洞(www.hetianlab.com)

    Docker是一个开源的引擎,可以轻松的为任何应用创建一个轻量级的、可移植的、自给自足的容器。开发者在笔记本上编译测试通过的容器可以批量地在生产环境中部署,包括VMs(虚拟机)、bare metal、OpenStack 集群和其他的基础应用平台。 产生原因 如果在docker上配置了远程访问,d

    2024年02月04日
    浏览(58)
  • wwwxxx域名选择(www.xxx.com或者.cn)

    域名就是网站的网址,就跟家庭住址一样,那么域名就是我们网站的地址,我们使用方便记忆的域名(字母/数字+.COM等域名后缀:www.xxx.com)。 按所属机构分 常见后缀形式: COM:商业性的机构/公司/个人,因为COM这个后缀公信度高,所以用得比较多 ORG :非盈利的组织、团体

    2024年02月05日
    浏览(67)
  • 实例35---字符串反转,如将字符串 “www.runoob.com“ 反转为 “moc.boonur.www“。

    本系列为C语言菜鸟100道基础经典例题详解刷题系列。点滴成长,一起逆袭。 实例35—字符串反转( 字符串数组逆序输出 ),如将字符串 “www.runoob.com” 反转为 “moc.boonur.www”。 对c语言的字符串进行反转,将abcdef反转为fedcba的办法有很多,而我所使用的方法是 for循环来将字

    2024年02月04日
    浏览(49)
  • 虚拟机 ping: www.baidu.com:未知的名称或服务

    1、打开ifcfg-ens33文件 2、如下,加上网关和dns就行了,紫色部分,也就是 DNS1=“114.114.114.114” 2.1、 注释: 2.2、网关怎么看,静态IP地址如何确定? 第一步:网关确定,打开虚拟机网络编辑器,找到vmnet8,里面就有个网关,自动获取的: 这个网关,就是我们要填的。 第二部:

    2024年02月06日
    浏览(55)
  • 为什么要给数据库加索引?转自 https: //blog.tankery.me/development/why-we-need-indexes-for-database

    这篇文章不是数据库索引的使用文档,不会给每个功能的使用都做介绍,而是通过我自己的案例,对案例中遇到的几个点做详细的说明。如果想查看具体的使用帮助,可以参考官网的文档:Query Planning “老谭,测试发现睡眠历史记录页面的打开速度太慢了,你给快速解决一下

    2024年02月03日
    浏览(38)
  • Restclient-cpp库介绍和实际应用:爬取www.sohu.com

    Restclient-cpp是一个用C++编写的简单而优雅的RESTful客户端库,它可以方便地发送HTTP请求和处理响应。它基于libcurl和jsoncpp,支持GET, POST, PUT, PATCH, DELETE, HEAD等方法,以及自定义HTTP头部,超时设置,代理服务器等功能。 本文将介绍如何使用Restclient-cpp库来实现一个简单的爬虫程序

    2024年02月07日
    浏览(38)
  • 配置hosts文件,输入某域名(www.XXX.com)时出现自己的页面

    1、以管理员身份运行记事本。 2、打开C:WindowsSystem32driversetc路径下的hosts文件 3、如果页面没有任何文件,点击如图的所有文件即可    4、打开文件,在最下面写上自己的ip和所用的域名即可。 (注意 :如果配置完之后依然没用,可以尝试清除浏览器本地缓存) 原理:    

    2024年02月13日
    浏览(49)
  • ubuntu网络连接不上,ping: www.baidu.com: 域名解析暂时失败

    有一次意外打断了某个包的下载,然后在网上捣腾杀死进程时可能错误重置一些配置,导致两个虚拟机都连不上网,时隔两个星期被逼无奈寻找联网方法。 具体情况: 右上角网络透明出现了个问号(图为正常情况) 先是试了ping www.baidu.com,结果报错 网上说是dns解析错误 解

    2024年01月18日
    浏览(49)
  • 解决 Burpsuite Error Proxy Failed to connect to www.com

    我的环境: win10,Burpsuite 2022 个人觉得 Burpsuite版本对此报错是没有影响的。 之前不知道从什么时候开始 Burpsuite 就一直出现这个问题。 发现所有国内的网站都可以访问,但是外网的全部都会 443。报错截图如图所示 一直没找到办法,Burp 官网论坛上说的是防火墙的问题,其实

    2024年02月13日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包