Leetcode 1032 Trie方式的疑问
来源：1-5 大厂面试为什么总考算法？
甲骨文_0001
2023-03-24
老师，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;
};
1回答
-
liuyubobobo
2023-03-28
我已经忘了我为什么对于这个问题的 trie 要这么实现了。但整体在当下我并不推荐这样实现树结构。（是的，这类实现可以作为通用的实现任何一棵树，而不局限于 trie 的实现。甚至这个思路可以用于实现任何一个图）。
如果一定要了解这个实现背后的原理，也并不难。这个实现的意思就是把树中的所有节点都排在一个数组中。这样一来，每个树的节点的子节点，就可以只存储一个数组的索引 index（而非一个节点的指针）。
以 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
继续加油！：）
012023-03-28
相似问题