Description:

I implemented a [Trie on Leetcode][1] and when I test it locally, running Node v16.15.1, the output of the test case I get does not match the output on LeetCode.

I ran the initial test case and my solution passed; however, when I submitted, the 8th test case failed. The test case attempts to search an empty Trie. When I attempt this locally, my output is false; however, Leetcode returns true!

Leetcode Description:

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

[null, null, true, false, true, null, true]

Explanation

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

Test Case That Fails:

['Trie', 'search']
[[],'a']

My output:

[null, false] //expected output (correct)

Leetcode Output:

[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;
    }
}

CodePudding user response：

The problem is caused in the search method. It does not consistently return a boolean, but can return null.

So change this:

search(word){
    let node = this.#getLastNode(word); 
    return (node && node.isWord); 
}

to:

search(word){
    let node = this.#getLastNode(word); 
    return !!node && node.isWord; 
}