// 节点 var TrieNode = function ( val = ""){ // 一个节点只保存一个值 this.val = val // 用来存储子节点 this.children = {} // 标记单词结束 this.isWord = false }
// 向当前节点添加子节点 TrieNode.prototype.add = function( val ){ let child = new TrieNode( val ) this.children[val] = child returnthis.children[val] }
/** * Initialize your data structure here. */ var Trie = function() { this.root = new TrieNode("") };
/** * Inserts a word into the trie. * @param {string} word * @return {void} */ Trie.prototype.insert = function(word) { let current = this.root let words = word.split("") for( let item of words ){ if( current.children[ item ] ){ current = current.children[item] } else { current = current.add( item ) } } current.isWord = true };
/** * Returns if the word is in the trie. * @param {string} word * @return {boolean} */ Trie.prototype.search = function(word) { let current = this.root let words = word.split("") for( let item of words ){ if( current.children[item] ){ current = current.children[item] } else { returnfalse } } return current.isWord };
/** * 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 current = this.root let prefixs = prefix.split("") for( let item of prefixs ){ if( current.children[item] ){ current = current.children[item] } else { returnfalse } } returntrue };