描述:
我实现了[Trie-on-Leetcode][1],当我在本地测试它时,运行Node v16.15.1,我得到的测试用例的输出与Leetcode上的输出不匹配。
我运行了最初的测试用例,我的解决方案通过了;然而,当我提交时,第8个测试用例失败了。测试用例尝试搜索空的Trie。当我在本地尝试此操作时,我的输出为false;然而,Leetcode返回true!
Leetcode描述:
trie(发音为"try")或前缀树是一种用于在字符串数据集中有效存储和检索密钥的树数据结构。这种数据结构有多种应用程序,如自动完成和拼写检查器。
实现Trie类:
Trie()初始化Trie对象。void insert(字符串)将字符串插入到trie中。boolean search(字符串单词)如果字符串单词在trie中(即之前插入),则返回true,否则返回false。boolean startsWith(字符串前缀)如果先前插入的字符串单词具有前缀前缀,则返回true,否则返回false。
示例1:
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
失败的测试用例:
['Trie', 'search']
[[],'a']
我的输出:
[null, false] //expected output (correct)
Leetcode输出:
[null, true]//unexpected output (incorrect)
class Node{
char;
isWord;
children;
constructor(c){
this.char = c;
this.isWord = false;
//hash table
this.children = {};
}
}
class Trie{
root;
/**
* Trie (prefix tree) data structure.
*/
constructor(){
/**Create a root node.
* We don't actually store any characters in the
* root node.
*/
this.root = new Node('/0');
}
/**
* Insert a word to the trie
* @param {string} word word
*/
insert(word){
let curr = this.root;
for(let i = 0; i < word.length; i++){
let c = word[i];
/**Check to see if the character has been inserted */
if(!curr.children[c]){
curr.children[c] = new Node(c);
}
curr = curr.children[c];
}
/** now that we have inserted all the nodes,
* we set isWord to true in the current node*/
curr.isWord = true;
}
/**
* Search for word in trie.
* @param {string} word word
* @returns boolean
*/
search(word){
let node = this.#getLastNode(word);
/**Boolean -- if we found a node and if it's a word. */
return (node && node.isWord);
}
/**
* Checks to see if the word passed is a prefix.
* @param {string} prefix prefix
* @returns Boolean
*/
startsWith(prefix){
return this.#getLastNode(prefix) != null;
}
/**
* Private Helper function
* Gets last node of a word.
* @param {string} word word
*/
#getLastNode(word){
let curr = this.root;
for (let i = 0; i < word.length; i++) {
const c = word[i];
if(!curr.children[c]){
return null;
}
curr = curr.children[c];
}
return curr;
}
}
问题是由search
方法引起的。它不一致地返回布尔值,但可以返回null
。
所以改变这个:
search(word){
let node = this.#getLastNode(word);
return (node && node.isWord);
}
至:
search(word){
let node = this.#getLastNode(word);
return !!node && node.isWord;
}