208. 实现 Trie (前缀树)（JS实现）
208. 实现 Trie (前缀树)（JS实现）
1 题目
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
2 思路
这道题就是实现前缀树这种数据结构，这种数据结构有个特点，就是每个节点存储一个元素为指针的数组，数组的索引就指明当前的字母，而数组值就指向下一个指针数组。
3代码
/**
* Initialize your data structure here.
*/
var Trie = function() {
this.startIndex = ‘a’.charCodeAt();
this.root = new TreeNode();
};
/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
let p = this.root;
for (let i=0; i<word.length; i++) {
let index = word[i].charCodeAt() – this.startIndex;
if (!p.list[index]) {
let newNode = new TreeNode();
p.list[index] = newNode;
}
p = p.list[index];
}
p.type = ‘leaf’;
p.word = word;
};
/**
* Returns if the word is in the trie.
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
let p = this.root;
for (let i=0; i<word.length; i++) {
p = p.list[word[i].charCodeAt() – this.startIndex];
if (!p && i<word.length-1) return false;
}
if (p && p.type === ‘leaf’ && p.word === word) return true;
return false;
};
/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
let p = this.root;
for (let i=0; i<prefix.length; i++) {
p = p.list[prefix[i].charCodeAt() – this.startIndex];
if (!p) return false;
}
return true;
};
function TreeNode() {
this.type = ‘branch’;
this.list = [];
this.word = ”;
}
/**
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
*/