肇庆市专注网站建设平台,如何用源代码做网站,网站设计的需求,美妆网站模板前言
今天学到关于路由相关文章#xff0c;发现动态路由中有一个很常见的实现方式是前缀树#xff0c;很感兴趣这个算法#xff0c;故进行记录。
前缀树 Trie#xff08;又被叫做字典树#xff09;可以看作是一个确定有限状态自动机#xff0c;尽管边上的符号一般是隐含…前言
今天学到关于路由相关文章发现动态路由中有一个很常见的实现方式是前缀树很感兴趣这个算法故进行记录。
前缀树 Trie又被叫做字典树可以看作是一个确定有限状态自动机尽管边上的符号一般是隐含在分支的顺序中的。 这里埋下一个坑有时间我会去写一篇关于状态机的文章。 这里我们看到每一个节点的所有的子节点都拥有相同的前缀这样我们可以通过前缀进行分段的路由匹配。 使用js实现前缀树
class TrieNode {constructor() {this.children {}; // 存储子节点this.isEndOfWord false; // 标记是否是单词的结尾this.num 0}
}class Trie {constructor() {this.root new TrieNode(); // 创建根节点}// 向前缀树中插入一个字符串insert(word) {let node this.root;for (let i 0; i word.length; i) {const char word[i];if (!node.children[char]) {node.children[char] new TrieNode();}node node.children[char];}node.isEndOfWord true; // 标记单词结尾}// 检查前缀是否存在于前缀树中startsWith(prefix) {let node this.root;for (let i 0; i prefix.length; i) {const char prefix[i];if (!node.children[char]) {return false; // 前缀不存在}node node.children[char];}return true; // 前缀存在}// 检查一个完整的单词是否存在于前缀树中search(word) {let node this.root;for (let i 0; i word.length; i) {const char word[i];if (!node.children[char]) {return false; // 单词不存在}node node.children[char];}node.num 1 //每被查一次次数就1return node.isEndOfWord; // 如果是单词的结尾返回true}
}
