Leetcode 208. 实现 Trie (前缀树) (Day 19) JavaScript

class Node{
constructor(){
this.son=Array(26).fill(null);
this.end=false;
}
}

class Trie{
constructor(){
this.root=new Node;
}

insert(word){
let cur=this.root;
for(let i of word){
i=i.charCodeAt(0)–'a'.charCodeAt(0);
if(!cur.son[i]) cur.son[i]=new Node();
cur=cur.son[i];
}
cur.end=true;
}

#find(string){
let cur=this.root;
for(let i of string){
i=i.charCodeAt(0)–'a'.charCodeAt(0);
if(!cur.son[i]) return 0;
cur=cur.son[i];
}
return cur.end?2:1;
}

search(string){
const flag=this.#find(string);
return flag===2?true:false;
}
startsWith(string){
const flag=this.#find(string);
return flag!=0?true:false;
}

}

var Trie = function() {
this.children = {};
};

Trie.prototype.insert = function(word) {
let nodes = this.children;
for (const ch of word) {//循环word
if (!nodes[ch]) {//当前字符不在子节点中 则创建一个子节点到children的响应位置
nodes[ch] = {};
}
nodes = nodes[ch];//移动指针到下一个字符子节点
}
nodes.isEnd = true;//字符是否结束
};

Trie.prototype.searchPrefix = function(prefix) {
let nodes = this.children;
for (const ch of prefix) {//循环前缀
if (!nodes[ch]) {//当前字符不在子节点中 直接返回false
return false;
}
nodes = nodes[ch];//移动指针到下一个字符子节点
}
return nodes;//返回最后的节点
}

Trie.prototype.search = function(word) {
const nodes = this.searchPrefix(word);
//判断searchPrefix返回的节点是不是字符串的结尾的字符
return nodes !== undefined && nodes.isEnd !== undefined;
};

Trie.prototype.startsWith = function(prefix) {
return this.searchPrefix(prefix);
};

两种写法,本质遍历26叉树,类比在二叉树中搜索