精华内容
下载资源
问答
  • Trie树及其优化
    2021-10-10 17:08:06

    1 Trie树简介

    Trie又称前缀树或字典树,有如下特性:

    • 除根节点为空外,其每个节点都表示一个字符
    • 一个节点的所有子孙都有相同的前缀
    • 从根节点出发,到某一end节点,则表示一个字符串

    一下是一个简单的例子:在trie树中插入多个子串[she, he, her, this, his, is]

    在这里插入图片描述

    蓝色的节点表示end节点,即从root出发到end节点表示一个子串。

    当我们要查找主串sherthis,是否存在一个从首字符起前缀相同的子串时(如果是查找子串,则需要为trie加上fail指针,即AC自动机,这里不讲),我们便可以在trie上以O(n)的时间复杂度完成查找。

    从上边的例子中,我们可以看到在前缀匹配中,trie拥有不俗查找效率外,还能够对公共前缀进行空间上的压缩。

    Trie树主要可以应用在各种字符串前缀匹配的场景下,如搜索提示、词频统计等。

    看完后依然不明白,可以手动实现一遍LeetCode208题。

    2 比较

    2.1 HashMap

    HashMap可以在O(1)的时间复杂度和O(n)的时间复杂度内,完成对字符串的匹配。

    但其只能使用在字符串精确匹配,而无法应对前缀匹配场景。

    2.2 ElasticSearch

    除了自己实现数据结构去应对业务场景外,同样可以考虑借助一些中间件帮助我们干活。

    ElasticSearch作为一款分布式搜索引擎,是否能够实现高效的前缀匹配呢?

    ES提供有prefix前缀查询功能,可以支持前缀匹配功能。以匹配W1前缀为例,工作流程如下:

    1. 扫描词列表并查找第一个以W1开始词
    2. 搜集关联的文档ID
    3. 移动到下一个词
    4. 如果这个词也是以W1开头,查询跳回到第二步再重复执行,直到下一词不以W1为止

    但官方文档中同时也建议要小心使用该功能,避免搜索过大的词集合(换句话说,也就是输入的前缀能够匹配上的词越少,效率越高)。

    prefix 查询或过滤对于一些特定的匹配是有效的,但使用方式还是应当注意。当字段中词的集合很小时,可以放心使用,但是它的伸缩性并不好,会对我们的集群带来很多压力。可以使用较长的前缀来限制这种影响,减少需要访问的量。

    所以可以看到ElasticSearch可以解决前缀匹配的问题,但是要考虑前缀串的特性,并且要依赖中间件。

    3 实现Trie树

    这里就不贴实现了,网上的代码有很多。

    如果你思考过如何实现Trie树,或则尝试解决了LeetCode208题,你或许发现可以使用HashMap或则数组去存储父子节点关系。

    但不幸的是,在特定的业务场景和数据量比较小的情况,它们能够正确的运行。但数据量太大的话,这两种实现恐怕就无法胜任工作了。

    使用HashMap需要new大量的对象,对GC并不友好,并且hashMap自身的数据结构对内存的占用较高。

    使用数组则不够灵活,因为插入的字符可不一定是26个英文字符,数组大小难以估算,并且哪怕是只有一个子节点,也需要开辟一个完整的数组。

    那有没有一种在O(1)时间复杂度下,能以更小的空间复杂度实现父子节点关系的存储呢?

    有,它便是双数组(DoubleArrayTrie)。

    4 使用DoubleArrayTrie降低空间复杂度

    简单的说,DoubleArrayTrie本质是一个确定有限状态自动机(DFA),使用两个线性数组(base数组和check数组)来表示Trie树,对Trie的结构进行了空间上的压缩,但同时不降低查询速度。

    在这里不做更多DoubleArrayTrie构建和查找原理上的介绍,感兴趣这里贴几篇高质量的文章(让我写并不会写得比他们更好),足够让你理解DoubleArrayTrie的原理和实现了。

    《DoubleArrayTrie的Java实现》

    《最好懂的DoubleArrayTrie构建与遍历流程》

    《计算的本质:深入剖析程序和计算机》3.1节 确定性有限自动机

    更多相关内容
  • DoubleArrayTrie 双端trie树的python实现 版本翻译于 将其改写成python3.5版本 ...在存储值很多且多有冲突、字符编码范围较大的情况下,双数组Trie树很可能在序列化到硬盘以及加载到内存的占用空间都远大于字典Trie树
  • 有时,我们会碰到对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(n*lgn),但若采用Trie树,则时间复杂度仅为O(n)
  • 为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP路由算法的基础上,提出一种基于多分枝trie树的改进路由查找算法。在多分枝trie树中取消前缀查找,组成一个大的中间结点。...
  • Trie树

    2021-01-29 21:26:00
    Trie树是为匹配字符串而准备的,所以我们需要预先建立一个Trie树: 构造Trie树 但实际上构造Trie树,是利用数组(每个节点是字符值+下一字符的索引): 纯26个小写英文字母匹配,可以通过字符的 ASCII 码减去“a...

    基本概念

    Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。

    Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起:
    在这里插入图片描述

    Trie树的操作

    Trie树是为匹配字符串而准备的,所以我们需要预先建立一个Trie树:

    构造Trie树

    在这里插入图片描述
    在这里插入图片描述
    但实际上构造Trie树,是利用数组(每个节点是字符值+下一字符的索引):
    在这里插入图片描述
    纯26个小写英文字母匹配,可以通过字符的 ASCII 码减去“a”的 ASCII 码,迅速找到匹配的子节点的指针。

    //纯26个英文字母的匹配
    public class Trie {
      private TrieNode root = new TrieNode('/'); // 存储无意义字符
    
      // 往Trie树中插入一个字符串
      public void insert(char[] text) {//text是字符串的toCharArray();
        TrieNode p = root;
        for (int i = 0; i < text.length; ++i) {
          int index = text[i] - 'a';
          if (p.children[index] == null) {
            TrieNode newNode = new TrieNode(text[i]);
            p.children[index] = newNode;
          }
          p = p.children[index];
        }
        p.isEndingChar = true;
      }
    
      // 在Trie树中查找一个字符串
      public boolean find(char[] pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length; ++i) {
          int index = pattern[i] - 'a';
          if (p.children[index] == null) {
            return false; // 不存在pattern
          }
          p = p.children[index];
        }
        if (p.isEndingChar == false) return false; // 不能完全匹配,只是前缀
        else return true; // 找到pattern
      }
    
      public class TrieNode {
        public char data;
        public TrieNode[] children = new TrieNode[26];
        public boolean isEndingChar = false;
        public TrieNode(char data) {
          this.data = data;
        }
      }
    }
    

    时间复杂度分析

    构建Trie树时间复杂度是 O(n)(n是Trie树中所有元素的个数)
    查询Trie树时间复杂度是 O(k)(k 表示要查找的字符串的长度)

    Trie树缺点

    1. 每个数组元素要存储一个 8 字节指针(或者是 4 字节,这个大小跟 CPU、操作系统、编译器等有关),且指针对CPU缓存并不友好。
    2. 在重复的前缀并不多的情况下,Trie 树不但不能节省内存,还有可能会浪费更多的内存。(比如,此种字符串第三个字符只有两种可能,而它要维护一个长26的数组。这还只是考虑纯字母的情况,如果是复合型字符串,则会浪费更多空间)

    解决办法:

    方法一: 将每个节点中的数组换成其他数据结构,比如有序数组、跳表、散列表、红黑树等。
    假设我们用有序数组,数组中的指针按照所指向的子节点中的字符的大小顺序排列。通过二分查找的方法,快速查找到某个字符应该匹配的子节点的指针。(这就不用维护一个上述26的数组,只需要维护两个可能的字符数组)当然,这样为了维护数组顺序,插入元素效率较慢。

    方法二:缩点优化
    在这里插入图片描述

    应用

    Trie 树实际上表现得并不好:

    第一,字符串中包含的字符集不能太大。如果字符集太大,那存储空间可能就会浪费很多。即便可以优化,但也要付出牺牲查询、插入效率的代价。

    第二,要求字符串的前缀重合比较多,不然空间消耗会变大很多。

    第三,通过指针串起来的数据块是不连续的。所以,对缓存并不友好,性能上会打个折扣。

    我们在工程中,更倾向于用散列表或者红黑树。因为这两种数据结构,我们都不需要自己去实现,直接利用编程语言中提供的现成类库就行了。

    实际上,Trie 树只是不适合精确匹配查找,这种问题更适合用散列表或者红黑树来解决。 Trie 树比较适合的是查找前缀匹配的字符串(如 实现搜索引擎的搜索关键词提示功能)。

    如何利用 Trie 树,实现搜索关键词的提示功能?

    在这里插入图片描述
    Trie 树的这个应用可以扩展到更加广泛的一个应用上,就是自动输入补全,比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。


    匹配算法

    单模式串匹配算法,是在一个模式串和一个主串之间进行匹配,也就是说,在一个主串中查找一个模式串。

    多模式串匹配算法,就是在多个模式串和一个主串之间做匹配,也就是说,在一个主串中查找多个模式串。(AC自动机)


    AC自动机

    1. 先要构建一个敏感词字典树Trie树
    2. 只需要遍历一遍文本就能找出所有的敏感词
      在这里插入图片描述

    实现

    树结点:

    public class AcNode {
      public char data; 
      public AcNode[] children = new AcNode[26]; // 字符集只包含a~z这26个字符
      public boolean isEndingChar = false; // 结尾字符为true
      public int length = -1; // 当isEndingChar=true时,记录模式串长度
      public AcNode fail; // 失败指针
      public AcNode(char data) {
        this.data = data;
      }
    }
    
    1. 构建树:
    	private AcNode root = new AcNode('/'); // 存储无意义字符
    	
    // 往Trie树中插入一个字符串
        public void insert(char[] text) {
            AcNode p = root;
            for (int i = 0; i < text.length; ++i) {
                int index = text[i] - 'a';
                if (p.children[index] == null) {
                    AcNode newNode = new AcNode(text[i]);
                    p.children[index] = newNode;
                }
                p = p.children[index];
            }
            p.isEndingChar = true;
        }
    
    1. 构建fail指针:
    //构建fail指针
        public void buildFailurePointer() {
            Queue<AcNode> queue = new LinkedList<>();
            root.fail = null;
            queue.add(root);
            while (!queue.isEmpty()) {
                AcNode p = queue.remove();
                for (int i = 0; i < 26; ++i) {
                    AcNode pc = p.children[i];
                    if (pc == null) continue;
                    if (p == root) {
                        pc.fail = root;
                    } else {
                        AcNode q = p.fail;
                        while (q != null) {
                            AcNode qc = q.children[pc.data - 'a'];
                            if (qc != null) {
                                pc.fail = qc;
                                break;
                            }
                            q = q.fail;
                        }
                        if (q == null) {
                            pc.fail = root;
                        }
                    }
                    queue.add(pc);
                }
            }
        }
    
    1. 进行文本匹配:
    //匹配文本字符串
        public void match(char[] text) { // text是主串
            int n = text.length;
            AcNode p = root;
            for (int i = 0; i < n; ++i) {
                int idx = text[i] - 'a';
                while (p.children[idx] == null && p != root) {
                    p = p.fail; // 失败指针发挥作用的地方
                }
                p = p.children[idx];
                if (p == null) p = root; // 如果没有匹配的,从root开始重新匹配
                AcNode tmp = p;
                while (tmp != root) { // 打印出可以匹配的模式串
                    if (tmp.isEndingChar == true) {
                        int pos = i-tmp.length+1;
                        System.out.println("匹配起始下标" + pos + "; 长度" + tmp.length);
                    }
                    tmp = tmp.fail;
                }
            }
        }
    

    复杂度分析

    匹配的时间复杂度是 O(n*len)。(n字符数量,len是Trie的高度,即字符串长度)因为敏感词并不会很长,所以实际情况下,近似于 O(n),所以 AC 自动机做敏感词过滤,性能非常高。

    从时间复杂度上看,AC 自动机匹配的效率跟 Trie 树一样啊。
    实际上,因为失效指针可能大部分情况下都指向 root 节点,所以绝大部分情况下,在 AC 自动机上做匹配的效率要远高于刚刚计算出的比较宽泛的时间复杂度。只有在极端情况下,如图所示,AC 自动机的性能才会退化的跟 Trie 树一样。
    在这里插入图片描述

    展开全文
  • 主要介绍了PHP字典树(Trie树)定义与实现方法,简单描述了字典树的概念并结合实例形式分析了字典树的定义与使用方法,需要的朋友可以参考下
  • 主要介绍了Java中实现双数组Trie树实例,双数组Trie就是一种优化了空间的Trie树,本文给出了实现代码、测试代码和测试结果,需要的朋友可以参考下
  • Python实现Trie树

    2018-06-13 11:00:23
    用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...
  • datrie, 快速高效的python 存储Trie树 使用 libdatrie datrie 超快速。高效的python ( 2.x 和 3. x ) 存储 Trie 。 使用 libdatrie 。安装pip install datrie用法创建一个新的trie,可以存储小写
  • 一个简单的C语言程序:用Trie树实现词频统计和单词查询
  • Trie树是一种很常用的树结构,它被广泛用于各个方面,比如字符串检索、中文分词、求字符串最长公共前缀和字典排序等等,而且在输入法中也能看到Trie树的身影。 什么是Trie树 Trie树通常又称为字典树、单词查找树或...
  • trie树的实现(C)

    2015-05-18 17:13:51
    trie.c中定义了trie树的操作函数; trie.h为相应的头文件; test.c用于测试相关的函数。 在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,...
  • Trie树,又叫字典树、前缀树(Prefix Tree)、单词查找树 或 键树,是一种多叉树结构。如下图: 好比假设有b,abc,abd,bcd,abcd,efg,hii 这6个单词,那我们创建trie树就得到 上图可以归纳出 Trie 树的基本...

    目录

    什么是前缀树

    前缀树的优缺点:

    前缀树的应用


    什么是前缀树

    Trie树,即字典树,又称单词查找树或键树,是一种多叉树结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较。如下图:

    好比假设有b,abc,abd,bcd,abcd,efg,hii 这6个单词,那我们创建trie树就得到

    上图可以归纳出 Trie 树的基本性质:

    1. 根节点不包含字符,除根节点外的每一个子节点都包含一个字符。

    2. 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。

    3. 每个节点的所有子节点包含的字符互不相同。

    4. 若实现前缀树时用的是hash数组,如vector<Node*> child;   Node : child(26);则每个节点的子节点都是按字典序的,如上图根节点的孩子a->b->e->h。(这种前缀树就是字典树,可以用于按字典序输出树种的字符串。优点:可以按字典树输出字符串。缺点:占用空间大)

        若实现前缀树时用的是标准库hashmap:unordered_map<char, Node*> child,则每个节点的子节点不是按字典序的(优点:占用空间小。缺点:不能按字典树输出字符串),如下图:

    通常在实现的时候,会在节点结构中设置一个标志,用来标记该结点处是否构成一个单词(关键字)。

    可以看出,Trie 树的关键字一般都是字符串,而且 Trie 树把每个关键字保存在一条路径上,而不是一个结点中。另外,两个有公共前缀的关键字,在 Trie 树中前缀部分的路径相同,所以 Trie 树又叫做前缀树(Prefix Tree)。

    前缀树的优缺点

    Trie 树的核心思想是空间换时间,利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

    优点:

    1. 存储查询的都很高效,都为 O(m) ,其中 m 是待插入/查询的字符串的长度。常用于:
      1. 向前缀树中插入字符串word;
      2. 查询前缀串prefix是否为已经插入到前缀树中的任意一个字符串word的前缀;
    2. Trie 树中不同的关键字不会产生冲突。

    3. Trie 树只有在允许一个关键字关联多个值的情况下才有类似 hash 碰撞发生。

    4. Trie 树不用求 hash 值,对短字符串有更快的速度。通常,求 hash 值也是需要遍历字符串的。

    5. Trie 树可以对关键字按字典序排序(需要用hash数组实现)。

    缺点:

    1. 当 hash 函数很好时,Trie 树的查找效率会低于哈希搜索。

    2. 空间消耗比较大。

    前缀树的应用

    1,字符串检索

    检索/查询功能是Trie树最原始的功能,给定一组字符串,查找某个字符串是否出现过

    思路就是从根节点开始一个一个字符进行比较:

    (1) 如果沿路比较,发现不同的字符,则表示该字符串在集合中不存在。

    (2) 如果所有的字符全部比较完并且全部相同,还需判断最后一个节点的标志位(标记该节点是否代表一个关键字)。

    2,词频统计

    Trie树常被搜索引擎系统用于文本词频统计 。

    思路: 用整型变量 count 来计数。对每一个关键字执行插入操作,若已存在,计数加1,若不存在,插入后 count 置1。

    3,字符串排序

    Trie 树可以对大量字符串按字典序进行排序,思路也很简单:遍历一次所有关键字,将它们全部插入 Trie 树,树的每个结点所有子节点很显然地按照字母表排序,然后先序遍历输出 Trie 树中所有关键字即可。

    4,前缀匹配

    例如:找出一个字符串集合中所有以 ab 开头的字符串。我们只需要用所有字符串构造一个 Trie 树,然后输出以 a->b-> 开头的路径上的关键字即可。

    Trie 树前缀匹配常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

    前缀树基本结构及实现:

    // 字典树 -- hash 数组实现

    // 不释放内存版

    // 法1:树本身就是节点
    class Trie {
    public:
        Trie() : child(26) , isEnd(false) {
        }
    
        void insert(string word) {
            Trie* node = this;
            for (auto ch : word) {
                ch -= 'a';
                if (node->child[ch] == nullptr) {
                    node->child[ch] = new Trie;
                }
                node = node->child[ch];
            }
            node->isEnd = true;
        }
    
        bool search(string word) {
            Trie* matchNode = SearchPrefix(word);
            return matchNode != nullptr && matchNode->isEnd;
        }
    
        bool startsWith(string prefix) {
            Trie* matchNode = SearchPrefix(prefix);
            return matchNode != nullptr ? true : false;
        }
    private:
        vector<Trie*> child; // hash数组足额申请26节点内存, 可使子节点有序
        bool isEnd;
        Trie* SearchPrefix(string word)
        {
            Trie* node = this;
            for (auto ch : word) {
                ch -= 'a';
                if (node->child[ch] == nullptr) {
                    return nullptr;
                }
                node = node->child[ch];
            }
            return node;
        }
    };
    
    // 法2:树本身只包含根节点,节点结构在树外部实现
    namespace TrieTest1 {
        struct Node {
            vector<Node*> child; // hash数组足额申请26节点内存, 可使子节点有序
            Node() : child(26), isEnd(false) {};
            bool isEnd;
        };
        class Trie {
        public:
            Trie() {}
            void insert(string word) {
                Node* node = &root;
                for (auto ch : word) {
                    ch -= 'a';
                    if (node->child[ch] == nullptr) {
                        node->child[ch] = new Node;
                    }
                    node = node->child[ch];
                }
                node->isEnd = true;
            }
    
            bool search(string word) {
                Node* matchNode = SearchPrefix(word);
                return matchNode != nullptr && matchNode->isEnd;
            }
    
            bool startsWith(string prefix) {
                Node* matchNode = SearchPrefix(prefix);
                return matchNode != nullptr ? true : false;
            }
        private:
            Node root;
            Node* SearchPrefix(string word) {
                Node* node = &root;
                for (auto ch : word) {
                    ch -= 'a';
                    if (node->child[ch] == nullptr) {
                        return nullptr;
                    }
                    node = node->child[ch];
                }
                return node;
            }
        };
    };

    // 释放内存版

    // 树内部用pool记录所有申请过的节点指针,析构函数中遍历释放
    namespace TrieTest2 {
        struct Node {
            vector<Node*> child;
            Node() : child(26), isEnd(false) {};
            bool isEnd;
        };
        class Trie {
        public:
            Trie() {}
            ~Trie()
            {
                for (auto& nodePtr : pool) {
                    delete nodePtr;
                }
            }
    
            void insert(string word) {
                Node* node = &root;
                for (auto ch : word) {
                    ch -= 'a';
                    if (node->child[ch] == nullptr) {
                        node->child[ch] = new Node;
                        pool.push_back(node->child[ch]);
                    }
                    node = node->child[ch];
                }
                node->isEnd = true;
            }
    
            bool search(string word) {
                Node* matchNode = SearchPrefix(word);
                return matchNode != nullptr && matchNode->isEnd;
            }
    
            bool startsWith(string prefix) {
                Node* matchNode = SearchPrefix(prefix);
                return matchNode != nullptr ? true : false;
            }
        private:
            vector<Node*> pool;
            Node root;
            Node* SearchPrefix(string word)
            {
                Node* node = &root;
                for (auto ch : word) {
                    ch -= 'a';
                    if (node->child[ch] == nullptr) {
                        return nullptr;
                    }
                    node = node->child[ch];
                }
                return node;
            }
        };
    };

    // 前缀树--hashmap实现

    namespace TrieTest3 {
        struct Node {
            unordered_map<char, Node*> child; // 按存在的子节点申请内存, 子节点无序
            bool isEnd = false;
        };
        class Trie {
        public:
            Trie() {}
            void insert(string word) {
                Node* node = &root;
                for (auto ch : word) {
                    if (node->child.count(ch) == 0) {
                        node->child[ch] = new Node;
                    }
                    node = node->child[ch];
                }
                node->isEnd = true;
            }
    
            bool search(string word) {
                Node* matchNode = SearchPrefix(word);
                return matchNode != nullptr && matchNode->isEnd;
            }
    
            bool startsWith(string prefix) {
                Node* matchNode = SearchPrefix(prefix);
                return matchNode != nullptr ? true : false;
            }
        private:
            Node root;
            Node* SearchPrefix(string word)
            {
                Node* node = &root;
                for (auto ch : word) {
                    if (node->child.count(ch) == 0) {
                        return nullptr;
                    }
                    node = node->child[ch];
                }
                return node;
            }
    
        };
    };

    1,字符串检索 + 4,前缀匹配

    208. 实现 Trie (前缀树)

    如上前缀树基本结构及实现解法

    648. 单词替换

    思路:直接replace了原始串中前缀词。

    另一种解法是把原始串每个单词放入一个vector,用一个string res记录拼接结果,遍历vector若匹配了前缀,则用前缀拼接在res,否则用原单词拼接在res。

    struct Node {
        bool isEnd;
        string key;
        vector<Node*> child;
        Node() : child(26), isEnd(false) {};
    };
    class Trie {
    public:
        void AddNode(string &word)
        {
            Node* node = &trieRoot;
            for (auto ch : word) {
                ch -= 'a';
                if (node->child[ch] == nullptr) {
                    node->child[ch] = new Node;
                }
                node = node->child[ch];
            }
            node->isEnd = true;
            node->key = word;
        }
    
        Node* Search(string &word)
        {
            Node* node = &trieRoot;
            for (auto ch : word) {
                ch -= 'a';
                if (node->child[ch] == nullptr) {
                    return node;
                }
                node = node->child[ch];
                if (node->isEnd) {
                    return node;
                }
            }
            return node;
        }
    
    private:
        Node trieRoot;
    };
    
    class Solution {
    public:
        string replaceWords(vector<string>& dictionary, string sentence) {
            // 构建前缀树
            Trie trie;
            for (auto & word : dictionary) {
                trie.AddNode(word);
            }
    
            string eachWord;
            auto start = sentence.begin();
            for (auto start = sentence.begin(); start != sentence.end();) {
                if (isspace(*start)) {
                    start++;
                }
                auto wordEnd = find_if_not(start, sentence.end(), ::isalpha);
                string eachWord(start, wordEnd);
                Node* node = trie.Search(eachWord);
                if (!node->isEnd) {
                    start = wordEnd;
                    continue;
                }
                string prefix = node->key;
                int len = distance(sentence.begin(), start);
                sentence.replace(start, wordEnd, prefix);
                start = sentence.begin() + len + prefix.size();
            }
            return sentence;
        }
    };

    820. 单词的压缩编码

    思路:对words中每个word反转(["emit", "em", "lleb"]),并构建前缀树,把前缀树从根到叶上的word累加长度。

     在统计Trie树中从根到叶节点word时有三种方法:(时间复杂度都是\tiny O(\sum\ ^{w}i),法1耗时稍高,因为dfs又进行了一遍\tiny O(\sum\ ^{w}i)的耗时) 。

    法1:Trie树的每个node中用unordered_map记录child,对Trie进行dfs累加每个叶节点的深度,孩子节点为空时就是叶节点。

    struct Node {
        //string key;
        unordered_map<char, Node*> child;
    };
    class Trie {
    public:
        void AddNode(string &word)
        {
            Node* node = &trieRoot;
            for (int i = word.size() - 1; i >= 0; i--) {
                if (node->child.count(word[i]) == 0) {
                    node->child[word[i]] = new Node;
                }
                node = node->child[word[i]];
                //node->key = word;
            }
        }
        Node trieRoot;
    };
    
    class Solution {
    public:
        int minimumLengthEncoding(vector<string>& words) {
            // 构建trie
            Trie trie;
            for (auto& word : words) {
                trie.AddNode(word);
            }
    
            Dfs(&trie.trieRoot, 0);
            return res;
        }
        void Dfs(Node* node, int depth)
        {
            if (node->child.empty()) {
                //res += node->key.size() + 1; // 1 means '#'
                res += depth + 1;
                return;
            }
            for (auto& node : node->child) {
                Dfs(node.second, depth + 1);
            }
        }
    private:
        int res = 0;
    };

    法2(官网解答):Trie树的每个node中用hash vector还是hashmap记录child不重要,重要的是用count直接记录该node的孩子节点数量。在遍历words,构建Trie树时,用insert返回word的最后node和word在words中的idx一起记录在一个map中。对没有孩子节点的node的word累加长度。

    struct Node2 {
        vector<Node2*> child;
        int count = 0; // 本节点的孩子数, 孩子数为0,说明是叶节点也即是最长串
        Node2() : child(26) {};
    };
    class Trie2 {
    public:
        Node2* insert(string &word)
        {
            Node2* node = &trieRoot;
            for (int i = word.size() - 1; i >= 0; i--) {
                char ch = word[i] - 'a';
                if (node->child[ch] == nullptr) {
                    node->child[ch] = new Node2;
                    node->count++;
                }
                node = node->child[ch];
            }
            return node;
        }
        Node2 trieRoot;
    };
    
    class Solution2 {
    public:
        int minimumLengthEncoding(vector<string>& words) {
            unordered_map<Node2*, int> wordNodeIdxMap; // 记录每个word在Trie中最后node及其在原数组对应的idx
            int res = 0;
            // 构建trie
            Trie2 trie;
            for (int i = 0; i < words.size(); i++) {
                Node2* node = trie.insert(words[i]);
                wordNodeIdxMap[node] = i;
            }
    
            // 对无孩子的叶节点长度统计
            for (auto& ele : wordNodeIdxMap) {
                if (ele.first->count == 0) {
                    res += words[ele.second].size() + 1;
                }
            }
            return res;
        }
    };

    法3(甜姨解答):先对words进行按字符串长度从长到短排序,这样构建Trie树时,保证长word先构建好从根到叶的路径,后面的短子串在入Trie时肯定不能构建出一条新路径了。insert方法直接返回每条新路径对应word的长度,并累加。

    注:string/vector等容器的size()是O(1),但是list的size()方法可能是O(n)(跟gcc版本、是否-std=c++11及D_GLIBCXX_USE_CXX11_ABI宏有关STL 容器的 size() 方法的时间复杂度是多少? - 知乎

    struct TrieNode {
        vector<TrieNode*> child;
        TrieNode() : child(26) {};
    };
    
    class Trie1 {
    public:
        int insert(string& word)
        {
            int len = 0;
            TrieNode* node = &root;
            bool isNew = false;
            for (int i = word.size() - 1; i >= 0; i--) {
                if (node->child[word[i] - 'a'] == nullptr) {
                    isNew = true;
                    node->child[word[i] - 'a'] = new TrieNode;
                }
                node = node->child[word[i] - 'a'];
            }
            return isNew == true ? word.size() + 1 : 0;
        }
    private:
        TrieNode root;
    };
    
    class Solution1 {
    public:
        int minimumLengthEncoding(vector<string>& words) {
            sort(words.begin(), words.end(), [](string &s1, string &s2) {return s1.size() > s2.size();});
            // 构建trie
            Trie1 trie;
            int res = 0;
            for (auto& word : words) {
                res += trie.insert(word);
            }
    
            return res;
        }
    };

    211. 添加与搜索单词 - 数据结构设计

    思路:前缀树 + dfs。dfs时根据当前word[start],若为字母,则候选集就下一个node,若为'.',则候选集为child数组。

    struct Node {
        vector<Node*> child;
        int childCnt = 0;
        bool isEnd = false;
        Node() : child(26) {};
    };
    
    class WordDictionary {
    public:
        WordDictionary() {
        }
        void addWord(string word) {
            Node* node = &root;
            for (auto ch : word) {
                ch -= 'a';
                if (node->child[ch] == nullptr) {
                    node->child[ch] = new Node;
                    node->childCnt++;
                }
                node = node->child[ch];
            }
            node->isEnd = true;
        }
    
        bool search(string word) {
            int start = 0;
            bool res = BackTrack(word, start, &root);
            return res;
        }
        // dfs
        bool BackTrack(string& word, int start, Node* node)
        {
            if (start == word.size()) {
                if (node->isEnd == true || node->childCnt == 0) {
                    return true;
                } else {
                    return false;
                }
            }
    
            // 大剪枝
            if (node->childCnt == 0) {
                return false;
            }
            // word[start]为字母
            if (word[start] != '.' && node->child[word[start] - 'a'] == nullptr) {
                return false;
            }
    
            if (word[start] != '.' && node->child[word[start] - 'a'] != nullptr) {
                if (BackTrack(word, start + 1, node->child[word[start] - 'a'])) {
                    return true;
                }
            }
            // word[start]为'.'
            for (int i = 0; i < 26; i++) {
                if (word[start] == '.' && node->child[i] != nullptr) {
                    if (BackTrack(word, start + 1, node->child[i])) {
                        return true;
                    }
                }
            }
            return false;
        }
    private:
        Node root;
    };

    212. 单词搜索 II

    // 思路1:遍历words + board_backtrack

       算法:见lc79

       时间复杂度: O(words.length) * O(mn * 3^(words[i].length)) = 3 * 10^4 * 12 *12 * 3^10 = 255,091,680,000

    // 思路2:boards_backtrack + words_Trie

       算法:回溯到某pos时,不要用从起始点到pos的整个串到Trie中搜前缀串,而是回溯的过程中把Trie的node带到递归调用中。

            候选集:四个方向

            终止条件:当前pos不是words中任意单词的前缀,需要return(剪枝)

            收敛条件:当前pos是words中的一个单词,即node的isEnd为true,不需要return,继续检查pos后续的路径是否能匹配words中的一个其他单词

       时间复杂度:回溯的时间复杂度O(mn * 3^(words[i].length)) * searchTrie的时间复杂度O(1) = 12 *12 * 3^10 = 8,503,056

    // 思路2优化:边回溯边删除Trie的叶节点, 来缩小Trie上的节点数

    思路和算法

    考虑以下情况。假设给定一个所有单元格都是 a 的二维字符网格和单词列表 ["a", "aa", "aaa", "aaaa"] 。当我们使用方法一来找出所有同时

    在二维网格和单词列表中出现的单词时,我们需要遍历每一个单元格的所有路径,会找到大量重复的单词。

    为了缓解这种情况,我们在回溯的恢复现场阶段判断如果刚刚回溯回来的node是叶节点(若是原始完整路径的叶节点h(o->a->t->h),

    说明完整路径是一个word,那么该完整路径word在回溯之前已经记录在resSet中,为了避免从其他起始pos'o',重复遍历o->->t->h重复记录到resSet,所以删除该叶节点h;

    若是非完整路径叶节点t(o->a->t),那么oat也不是words中的word,也可删除该叶节点t),

    进行释放内存后删除,来缩小Trie节点数。

    struct Node {
        vector<Node*> child;
        int childCnt = 0;
        bool isEnd = false;
        string key;
        Node() : child(26) {};
    };
    class Trie {
    public:
        void insert(const string& word) {
            Node* node = &root;
            for (auto ch : word) {
                ch -= 'a';
                if (node->child[ch] == nullptr) {
                    node->child[ch] = new Node;
                    node->childCnt++;
                }
                node = node->child[ch];
            }
            node->isEnd = true;
            node->key = word;
        }
        Node root;
    };
    
    // 思路2:boards_backtrack + words_Trie // 936ms, 41%
    class Solution {
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            Trie trie;
            for (auto& word : words) {
                trie.insert(word);
            }
    
            unordered_set<string> resSet;
            vector<vector<int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
            vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
            for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board[0].size(); j++) {
                    BackTrack(i, j, board, &trie.root, dirs, visited, resSet);
                }
            }
            return vector<string>(resSet.begin(), resSet.end());
        }
    private:
        void BackTrack(int curL, int curC, vector<vector<char>>& board, Node* node, vector<vector<int>>& dirs,
            vector<vector<bool>>& visited, unordered_set<string>& resSet)
        {
            // 终止条件
            if (node->child[board[curL][curC] - 'a'] == nullptr) {
                return;
            }
            // 收敛条件
            if (node->child[board[curL][curC] - 'a']->isEnd == true) {
                resSet.insert(node->child[board[curL][curC] - 'a']->key);
            }
    
            visited[curL][curC] = true;
            // 遍历候选集
            for (auto& dir : dirs) {
                int nextL = curL + dir[0];
                int nextC = curC + dir[1];
                if (nextL < 0 || nextL >= board.size() || nextC < 0 || nextC >= board[0].size() || visited[nextL][nextC]) {
                    continue;
                }
                BackTrack(nextL, nextC, board, node->child[board[curL][curC] - 'a'], dirs, visited, resSet);
            }
            visited[curL][curC] = false;
        }
    };
    
    // 思路2优化:边回溯边删除Trie的叶节点, 来缩小Trie上的节点数 316ms 73.95%
    class Solution1 {
    public:
        vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
            Trie trie;
            for (auto& word : words) {
                trie.insert(word);
            }
    
            unordered_set<string> resSet;
            vector<vector<int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
            vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
            for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board[0].size(); j++) {
                    BackTrack(i, j, board, &trie.root, dirs, visited, resSet);
                }
            }
            return vector<string>(resSet.begin(), resSet.end());
        }
    private:
        void BackTrack(int curL, int curC, vector<vector<char>>& board, Node* node, vector<vector<int>>& dirs,
            vector<vector<bool>>& visited, unordered_set<string>& resSet)
        {
            // 终止条件
            if (node->child[board[curL][curC] - 'a'] == nullptr) {
                return;
            }
            // 收敛条件
            if (node->child[board[curL][curC] - 'a']->isEnd == true) {
                resSet.insert(node->child[board[curL][curC] - 'a']->key);
            }
            // 遍历候选集
            if (node->child[board[curL][curC] - 'a']->childCnt != 0) { // 这里的判断可写可不写,因为若childCnt == 0,则在接下来的回溯递归BackTrack的终止条件处这返回
                visited[curL][curC] = true;
                for (auto& dir : dirs) {
                    int nextL = curL + dir[0];
                    int nextC = curC + dir[1];
                    if (nextL < 0 || nextL >= board.size() || nextC < 0 || nextC >= board[0].size() || visited[nextL][nextC]) {
                        continue;
                    }
                    BackTrack(nextL, nextC, board, node->child[board[curL][curC] - 'a'], dirs, visited, resSet);
                }
                visited[curL][curC] = false;
            }
            // 删除Trie的叶节点
            if (node->child[board[curL][curC] - 'a']->childCnt == 0) {
                delete node->child[board[curL][curC] - 'a'];
                node->child[board[curL][curC] - 'a'] = nullptr;
            }
        }
    };

    745. 前缀和后缀搜索

    方法1:单独的前、后缀树 + hashmap

    思路:

    (1) 前缀树用于构建和查找prefix,后缀树用于构建和查找suffix。

    (2)构建树时,每个node用vector<int> idxVec记录words中各单词的索引。在前缀查找函数返回idxVec1,前缀查找函数返回idxVec2。归并idxVec1和idxVec2,排序,从后往前找第一个重复元素即是要找的满足同时找到前后缀的单词最大索引。

    (3)用3个hashmap记录已经找到的(prefix+“#” + suffix)、prefix、suffix,避免重复查找。

    时间复杂度:O(NK + Q(Nlog(N)+K))。其中N指的是单词的个数,K指的是单词中的最大长度,Q指的是搜索的次数。

    优化第(2)步中从两个idxVec1和idxVec2找公共最大算法:

    由于构建树时每个node中添加words中单词索引是正序添加的,因此索引在idxVec中越排在后面就越大因此,我们同时倒序遍历idxVec1和idxVec2

    优化后时间复杂度:O(NK + Q(N+K))。其中N指的是单词的个数,K指的是单词中的最大长度,Q指的是搜索的次数。

     优化前代码:(优化后的略)。优化前实际效果(应该是用例用有大量重复的prefix和suffix,用map找到后直接返回了,若不用map记录,则超时):

    执行用时: 444 ms, 49%

    内存消耗: 153.5 MB,57%

    struct Node {
        bool isEnd;
        vector<int> idxVec;
        vector<Node*> child;
        Node() : child(26), isEnd(false) {};
    };
    class Trie {
    public:
        void AddNode(string &word, int idx)
        {
            Node* preNode = &prefixRoot;
            for (auto ch : word) {
                ch -= 'a';
                if (preNode->child[ch] == nullptr) {
                    preNode->child[ch] = new Node;
                }
                preNode = preNode->child[ch];
                preNode->idxVec.push_back(idx);
            }
            preNode->isEnd = true;
    
            Node* subNode = &suffixRoot;
            for (int i = word.size() - 1; i >= 0; i--) {
                if (subNode->child[word[i] - 'a'] == nullptr) {
                    subNode->child[word[i] - 'a'] = new Node;
                }
                subNode = subNode->child[word[i] - 'a'];
                subNode->idxVec.push_back(idx);
            }
            subNode->isEnd = true;
        }
    
        vector<int> SearchPrefix(string &prefix)
        {
            Node* node = &prefixRoot;
            for (auto ch : prefix) {
                ch -= 'a';
                if (node->child[ch] == nullptr) {
                    return {};
                }
                node = node->child[ch];
            }
            return node->idxVec;
        }
    
        vector<int> SearchSuffix(string &suffix)
        {
            Node* node = &suffixRoot;
            for (int i = suffix.size() - 1; i >= 0; i--) {
                if (node->child[suffix[i] - 'a'] == nullptr) {
                    return {};
                }
                node = node->child[suffix[i] - 'a'];
            }
            return node->idxVec;
        }
    
    private:
        Node prefixRoot;
        Node suffixRoot;
    };
    
    class WordFilter {
    public:
        WordFilter(vector<string>& words) {
            for (int i = 0; i < words.size(); i++) {
                trie.AddNode(words[i], i);
            }
        }
    
        int f(string prefix, string suffix) {
            string tmpstr = prefix + "##" + suffix;
            if (mp.count(tmpstr)) {
                return mp[tmpstr];
            }
    
            vector<int> preIdxVec;
            if (prefixMap.count(prefix)) {
                preIdxVec = prefixMap[prefix];
            } else {
                preIdxVec = trie.SearchPrefix(prefix);
                prefixMap.insert({prefix, preIdxVec});
            }
    
            vector<int> subIdxVec;
            if (suffixMap.count(suffix)) {
                subIdxVec = suffixMap[suffix];
            } else {
                subIdxVec = trie.SearchSuffix(suffix);
                suffixMap.insert({suffix, subIdxVec});
            }
    
            copy(subIdxVec.begin(), subIdxVec.end(), back_inserter(preIdxVec));
            sort(preIdxVec.begin(), preIdxVec.end());
            for (int i = preIdxVec.size() - 1; i > 0; i--) {
                if (preIdxVec[i] == preIdxVec[i - 1]) {
                    mp[tmpstr] = preIdxVec[i];
                    return preIdxVec[i];
                }
            }
            mp[tmpstr] = -1;
            return -1;
        }
        Trie trie;
    private:
        unordered_map<string, int> mp;
        unordered_map<string, vector<int>> prefixMap;
        unordered_map<string, vector<int>> suffixMap;
    };

    方法2:后缀修饰的单词查找树 

     时间复杂度:O(NK^2 + QK)。其中 NN 指的是单词的个数,KK 指的是单词中的最大长度,Q 指的是搜索的次数。

    执行用时: 412 ms,53%

    内存消耗: 188.7 MB,32%

    namespace sol2 {
        struct Node {
            int maxIdx;
            vector<Node*> child;
            Node() : child(27), maxIdx(-1) {};
        };
    
        class Trie {
        public:
            void AddNode(vector<string>& words)
            {
                for (int idx = 0; idx < words.size(); idx++) {
                    string word = words[idx] + "#";
                    for (int i = 0; i < word.size(); i++) {
                        Node* node = &root;
                        for (int j = i; j < 2 * word.size() - 1; j++) {
                            int k = word[j % word.size()] == '#' ? 26 : word[j % word.size()] - 'a';
                            if (node->child[k] == nullptr) {
                                node->child[k] = new Node;
                            }
                            node = node->child[k];
                            node->maxIdx = idx;
                        }
                    }
                }
            }
    
            int SearchPrefix(string &prefix, string &suffix)
            {
                string fullStr = suffix + "#" + prefix;
                Node* node = &root;
                for (auto ch : fullStr) {
                    ch = ch == '#' ? 26 : ch - 'a';
                    if (node->child[ch] == nullptr) {
                        return -1;
                    }
                    node = node->child[ch];
                }
                return node->maxIdx;
            }
        private:
            Node root;
        };
    
        class WordFilter {
        public:
            WordFilter(vector<string>& words) {
                trie.AddNode(words);
            }
    
            int f(string prefix, string suffix) {
                return trie.SearchPrefix(prefix, suffix);
            }
        private:
            Trie trie;
        };
    }

    720. 词典中最长的单词

    // 方法:字典树

    // 思路:构建字典树,遍历时只筛选每个node都是end的节点(即是上个node添加一个字母得来的node),到了叶节点仅需比较长度,用长度大的更新res,因为相等长度的已经是字典序,无需更新res。

    struct Node {
        vector<Node*> child;
        bool isleaf = false;
        string str;
        Node() : child(26) {}
    };
    class Trie {
    public:
        void Insert(string& word)
        {
            Node* node = &root;
            for (auto ch : word) {
                if (node->child[ch - 'a'] == nullptr) {
                    node->child[ch - 'a'] = new Node;
                }
                node = node->child[ch - 'a'];
            }
            node->isleaf = 1;
            node->str = word;
        }
        Node root;
    };
    class Solution {
    public:
        void dfs(Node* node, string& res)
        {
            if (node == nullptr) {
                return;
            }
            if (!node->isleaf) {
                return;
            }
    
            if (node->str.size() > res.size()) { // 只需要比较长度, 在长度相等时因为字典遍历能保证字典序
                res = node->str;
            }
    
            for (auto ele : node->child) {
                dfs(ele, res);
            }
        }
        string longestWord(vector<string>& words) {
            Trie trie;
            for (auto& word : words) {
                trie.Insert(word);
            }
    
            string res;
            for (auto node : trie.root.child) {
                dfs(node, res);
            }
            return res;
        }
    };

    参考:

    数据结构与算法:字典树(前缀树) - 知乎

    展开全文
  • Python笔记:Trie树结构简介 Python笔记:Trie树结构简介 1. Trie树是什么 2. Trie树原理 3. Trie树代码实现 4. Leetcode例题分析 1. Leetcode 208. Implement Trie (Prefix Tree) 2. Leetcode 211. Design Add ...

    1. Trie树是什么

    Trie树又名字典树,前序查找树等等。本质来说,他就是一个确定有限状态自动机(DFA),从根节点往下到叶子节点的每一条路径都是一次有效搜索。

    通过Trie树,我们可以将搜索的时间复杂度大幅减小置近乎常数的量级。

    2. Trie树原理

    trie树的原理可以参考最后一章节中的参考链接里的几个博客说明,他们讲的都挺好的,配合下述原理图(图片来源于网上),相信理解Trie树的原理将完全不会有任何问题。

    Trie

    下面,我们直接来考察Trie树的代码实现。

    3. Trie树代码实现

    Trie树的代码实现事实上也不复杂,尤其是在使用python的情况下。他的本质事实上就是一个用字典构建的树。

    trie树最核心的功能包括以下两点:

    1. 插入新的词汇;
    2. 从字典中查询词汇;

    下面,给出最基本的代码实现如下:

    class Trie:
        def __init__(self):
            self.trie = {}
        
        def add_word(self, word):
            trie = self.trie
            for c in word:
                trie = trie.setdefault(c, {})
            trie["eos"] = ""
    
        def find(self, word):
            trie = self.trie
            for c in word:
                if c not in trie:
                    return False
                trie = trie[c]
            return "eos" in trie
    

    当然,上述只是最为简单的trie树功能实现,实际在使用中会存在多种变体,比如:

    • 纯前缀查找(不完全匹配)
    • 某前缀下的所有可能搜索结果
    • 给字典中每一个单词加入权重
    • ……

    下面,我们来结合leetcode上面的习题来对trie树进行一些更深入的讨论。

    4. Leetcode例题分析

    leetcode中有一个专门的Trie树的题目集合,目前有17道题目,其中3题被锁住了,剩余14题是全员可见的,拿来练手足够了。

    我们从中选取几道题目来浅谈一下Trie树的一些常规用法。

    相信如果把下面几道Leetcode中的Trie树的题目搞定的话,你对Trie树应该至少也有一个非常直观的理解了。

    1. Leetcode 208. Implement Trie (Prefix Tree)

    给出题目链接如下:https://leetcode.com/problems/implement-trie-prefix-tree/

    这一题算是Trie树的最基础例题了,他事实上就是要求你实现一下Trie树,并完成其中的完全匹配搜索与不完全匹配搜索。

    我们直接给出代码实现如下:

    class Trie:
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.cache = {}
            
    
        def insert(self, word: str) -> None:
            """
            Inserts a word into the trie.
            """
            cache = self.cache
            for c in word:
                cache = cache.setdefault(c, {})
            cache["eos"] = {}
            return
    
        def search(self, word: str) -> bool:
            """
            Returns if the word is in the trie.
            """
            cache = self.cache
            for c in word:
                if c not in cache.keys():
                    return False
                cache = cache[c]
            return "eos" in cache.keys()
            
    
        def startsWith(self, prefix: str) -> bool:
            """
            Returns if there is any word in the trie that starts with the given prefix.
            """
            cache = self.cache
            for c in prefix:
                if c not in cache.keys():
                    return False
                cache = cache[c]
            return True
    

    有了这部分的基础,我们后续就可以进行更多的实例考察了。

    2. Leetcode 211. Design Add and Search Words Data Structure

    给出题目链接如下:https://leetcode.com/problems/design-add-and-search-words-data-structure/

    这一题是上一题的变体,他的难度会更高一点,要求是允许.匹配任意一个字符,因此,每当遇到一次.,我们就需要遍历当前根下的所有节点,看是否存在正确的匹配

    本质上来说,就是要我们在匹配完成前序数组之后遍历Trie树中在该前缀条件下的所有可能的完全匹配结果。其中,前者我们通过trie树可以轻松实现,后者我们可以通过深度优先算法(dfs)来进行实现

    给出代码实现如下:

    class WordDictionary:
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.trie = {}
    
        def addWord(self, word: str) -> None:
            """
            Adds a word into the data structure.
            """
            trie = self.trie
            for c in word:
                trie = trie.setdefault(c, {})
            trie["eos"] = ""
            return
    
        def search(self, word: str) -> bool:
            """
            Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
            """
            n = len(word)
            def dfs(trie, i):
                if i == n:
                    return "eos" in trie
                if word[i] != '.':
                    if word[i] not in trie:
                        return False
                    else:
                        return dfs(trie[word[i]], i+1)
                else:
                    return any(dfs(trie[c], i+1) for c in trie.keys() if c != "eos")
                
            return dfs(self.trie, 0)
    

    这一题本质上就是需要在匹配了部分前序字符串之后遍历所有的可能匹配,这部分内容我们都可以通过Trie树加上dfs算法来实现。

    类似的leetcode题目还包括:

    1. 677. Map Sum Pairs
    2. 676. Implement Magic Dictionary
    3. 336. Palindrome Pairs

    其中,前两题和本题基本是完全一致的,仿照着做就行了,第三题多少稍微复杂点,但是一旦确定思路就是反向找到所有不完全匹配的字符串集合之后再考察其是否组合结果是否满足回文条件的话,那么本质上来说就又回到这一题的算法了,没有根本性的差别。

    有兴趣的读者可以自行尝试去做一下,这里就不再赘述了。

    3. Leetcode 1032. Stream of Characters

    给出题目链接如下:https://leetcode.com/problems/stream-of-characters/

    这一题事实上挺简单的,就是将前序查找变换后后续查找,我们在Trie树的元素加入过程中直接反序地将元素加入之后即可。

    给出代码实现如下:

    class Trie:
        def __init__(self):
            self.trie = {}
    
        def add(self, word):
            trie = self.trie
            for c in word:
                trie = trie.setdefault(c, {})
            trie["eos"] = ""
        
        def find(self, word):
            trie = self.trie
            for c in word:
                if "eos" in trie:
                    return True
                if c not in trie:
                    return False
                trie = trie[c]
            return "eos" in trie
    
    class StreamChecker:
    
        def __init__(self, words: List[str]):
            self.querys = ""
            self.trie = Trie()
            for word in words:
                self.trie.add(word[::-1])
    
        def query(self, letter: str) -> bool:
            self.querys = letter + self.querys
            return self.trie.find(self.querys)
    

    4. Leetcode 212. Word Search II

    给出题目链接如下:https://leetcode.com/problems/word-search-ii/

    这一题就是基于Trie树的一道纯应用题了,用的就是最基本的Trie树结果,但是需要结合栈的内容来实现邻接序列的遍历。

    给出代码实现如下:

    class Trie:
        def __init__(self, words):
            self.trie = {}
            for word in words:
                self.add(word)
                
        def add(self, word):
            trie = self.trie
            for c in word:
                trie = trie.setdefault(c, {})
            trie["eos"] = "eos"
            
        def find(self, word, mode="full"):
            trie = self.trie
            for c in word:
                if c not in trie:
                    return False
                trie = trie[c]
            if mode != "full":
                return True
            else:
                return "eos" in trie
    
    class Solution:
        def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
            have_visited = set()
            ans = set()
            stack = []
            n = len(board)
            m = len(board[0])
            trie = Trie(words)
            
            def dfs(row, col):
                nonlocal stack, have_visited, ans
                stack.append(board[row][col])
                have_visited.add((row, col))
                if not trie.find(stack, mode='half'):
                    stack.pop()
                    have_visited.remove((row, col))
                    return
                if trie.find(stack, mode='full'):
                    ans.add(''.join(stack))
                if row-1 >= 0 and (row-1, col) not in have_visited:
                    dfs(row-1, col)
                if row+1 < n and (row+1, col) not in have_visited:
                    dfs(row+1, col)
                if col-1 >= 0 and (row, col-1) not in have_visited:
                    dfs(row, col-1)
                if col+1 < m and (row, col+1) not in have_visited:
                    dfs(row, col+1)
                stack.pop()
                have_visited.remove((row, col))
                return
            
            for i in range(n):
                for j in range(m):
                    dfs(i, j)
            return list(ans)
    

    5. 参考链接

    1. WikiPedia: Trie树
    2. 知乎:浅谈trie树
    3. Trie树(Prefix Tree)介绍
    展开全文
  • Double Array Trie是TRIE树的一种变形,它是在保证TRIE树检索速度的前提下,提高空间利用率而提出的一种数据结构,本质上是一个确定有限自动机(deterministic finite automaton,简称DFA)。 所谓的DFA就是一个能实现...
  • 通过基于划分位构建无冲突哈希函数,实现对片上存储器有效的控制,攻击特征平均分配到trie树每层的多个组中。该结构可以在同一个芯片中实现流水并行地执行,获得比较大的吞吐量。理论及实验表明该方法在片上存储器一...
  • 关于本源码更详细的解释说明,请参见:http://blog.csdn.net/lemon_tree12138/article/details/49281865
  • 嵌入式系统中基于trie树的拼音输入法的实现,李巧红,,介绍一种中文拼音输入法的实现方式,着重讨论了字库的设计及基于Trie树检索方法的实现。Trie树是基于关键码空间分解的树结构,其内�
  • 5.trie树(字典树) 参考自leedcode宫水三叶姐姐和bilibili极客学院老师的思想 (1) 字典树的数据结构 字典树,即tire树,又称单词树或键树,是一种树形结构。 典型应用是用于统计和排序大量的字符串,所以常被应用...
  • Trie ——Golang实现

    2021-12-26 10:59:52
    Trie ——Golang实现
  • 双数组trie树详解

    2021-12-03 11:14:22
    目录双数组trie树的构建构建base array构建check array双数组trie树的查询 双数组trie树的构建 NLP中trie树常用于做快速查询,但普通的trie树由于要保存大量的节点信息,当储存的词量非常大时,不仅所占空间巨大,...
  • C++实现Trie

    2021-11-30 12:18:53
    Trie 的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起 主要有两个操作, 一个是将字符串集合构造成 Trie 另一个是在 Trie 中查询一个字符串 我们不可否认,Trie 可能很浪费内存,但是确实...
  • 什么是Trie树 Trie树,又叫做字典树,顾名思义它是一种树形的数据结构。Trie树可以做到在一个字符串集合中快速匹配字符串,在构建之后也可以用于词频统计等。 背景 有这样一份数据,它包含了一系列Mac OS系统中的...
  • Trie (数据结构)

    2022-01-23 10:29:53
    1.Trie树的概念 Trie树是数据结构比较简单的一种。Trie 树的基本用法是高效的存储和查找字符串集合的数据结构。Trie树也叫做字典树,它是一个树形结构。是一种专门处理字符串匹配的数据结构,用来解决在一组字符串...
  • Trie树c++实现

    2022-02-16 22:26:31
    Trie树简介 Trie树又称字典树,是一种用于实现字符串快速检索的多叉树结构。Trie树的每个节点都有若干个字符指针,若在插入或检索字符串时扫描到一个字符c,就沿着当前节点的c这个字符指针,走向该指针指向的节点。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 42,854
精华内容 17,141
关键字:

trie树

友情链接: 单纯形法代码.zip