Leetcode 1032 Trie方式的疑问

Question

老师，1032题您的思路是trie,但是和算法体系课上的trie实现方式不一样，课上的实现方式是多叉树，多叉树的方案清楚好懂，而github题解上您用的是一个vector数组来承载trie,看了代码，没懂, 可以讲下吗，这个思路挺有用的。 这是一个求后缀的问题，我直接用了语言库里的字符串自带的endsWith函数来求解的。

=============
另外官方题解中还讲到了 AC自动机，可以稍作介绍吗…^-…

/**
 * @param {string[]} words
 */
var StreamChecker = function(words) {
    this.words = words;
    this.stream = ''; // 初始字符流, 从空字符串开始
};

/** 
 * @param {character} letter
 * @return {boolean}
 */
StreamChecker.prototype.query = function(letter) {
    this.stream += letter; // 不断往stream中添加字符

    // 遍历words数组来 判断数组中是否有字符流后缀
    for( let i = 0; i < this.words.length; i ++ ){
        if( this.stream.endsWith(this.words[i]) ){ // 通过String.prototype.endsWith原生方法来判后缀
            return true;
        }
    } // for i
    return false;
};

Answer 1

liuyubobobo 2023-03-28 06:33:32

我已经忘了我为什么对于这个问题的 trie 要这么实现了。但整体在当下我并不推荐这样实现树结构。（是的，这类实现可以作为通用的实现任何一棵树，而不局限于 trie 的实现。甚至这个思路可以用于实现任何一个图）。

如果一定要了解这个实现背后的原理，也并不难。这个实现的意思就是把树中的所有节点都排在一个数组中。这样一来，每个树的节点的子节点，就可以只存储一个数组的索引 index（而非一个节点的指针）。

https://github.com/liuyubobobo/Play-Leetcode/blob/master/1001-1500/1032-Stream-of-Characters/cpp-1032/main.cpp

以 40 行为例：treeID = trie[treeID].next[c]; 得到了以 treeID 为索引的节点的字母 c 对应的节点的索引，循环回到 35 行，就会开始访问 trie[treeID]，即上一个 treeID 字母 c 对应的子节点。

所以，36 行和 37 行加入一个节点，36 行赋值，赋的就是 37 行新创建的节点的索引（再添加这个节点前的 trie.size()）

这个技巧在一些时候可以提高一些性能，因为所有的节点被压缩在了一个数组中存储，在数组中使用索引获取元素比使用指针在内存中找元素要快。但对于现代计算机来说，这个性能提升并不敏感，属于常数级别的优化，而不是算法上的复杂度级别的提升。而这个做法本身是存在问题的，问题就在于删除元素以后会造成空间的浪费，所以其实在实际中并不实用。了解就好，我个人并不认为意义那么大。

==========

如果我能在问答区随便说两句话就给你讲清楚 AC 自动机，这个东西也就太简单了。反正我没有这个能力。实际上 AC 自动机复杂到很多文章长篇大论，很多同学都根本看不明白（或者可能是没有耐心去看明白。）比如这种文章在我看来介绍的就可以：https://oi-wiki.org/string/ac-automaton/

但是好消息是，一切基于“状态机”这个概念的算法（只是算法），对于一般软件工程师来说，根本不需要。很多知名的算法和数据结构教材也根本不会收录对这个算法的讲解，肯定是有原因的。（在我的印象里，无论是算法导论还是算法4，都没有介绍 AC 自动机。）

但注意，我只是强调算法，状态机本身对应一种设计模式（状态模式），状态模式是应该了解的（并且其实非常简单），在我看来，对于软件设计来说，是常用的。但是设计一个状态模式的代码，和使用状态机解决算法问题，完全是两个概念。

一旦把状态机搬到算法与数据结构领域中来，大多数同学头晕的根本原因是，根本没有“从头”接触基于状态机的算法是怎么一点一点从能解决简单的问题，到如此复杂的。实际上，在我看来，这个过程对应了一个领域：形式语言。（而形式语言是编译原理的理论基础，所以如果你不深入研究编译原理，根本不需要学习形式语言。）所以如果你真的想很透彻的理解这类基于状态机的算法，我的建议是去学习形式语言。

依然是，如果不感兴趣，或者没有时间去学，完全不影响 99.99% 的软件工程师的工作。这个算法本身太“领域相关了”。别说 AC 自动机了，在我看来，KMP 算法都是“领域相关”的，大多数软件工程师完全可以不了解（实际上我基本上也没听说过面试问 KMP 的）。可以参考我的这个回答：https://class.imooc.com/course/qadetail/343322

继续加油！：）

• 提问者 甲骨文_0001 #1

  谢谢老师的耐心讲答，受益了。我工作中确实用不到这种状态机，不过我想问下，算法体系课中kmp最后会上自动机的讲解吗，就当入个门:)