Published on

[LeetCode 208] Implement Trie (Prefix Tree)

Problem

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

Constraints:

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

TypeScript

class TrieNode {
    children: Map<string, TrieNode>;
    isEnd: boolean;
    
    constructor(){
        this.children = new Map<string, TrieNode>()
        this.isEnd = false;
    }
}

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

    insert(word: string): void {
        let cur: TrieNode = this.root;
        for(let c of word){
            if(!cur.children.has(c)) cur.children.set(c, new TrieNode())
            cur = cur.children.get(c)
        }
        cur.isEnd = true;
    }

    search(word: string): boolean {
        let cur: TrieNode = this.root;
        for(let c of word){
            if(!cur.children.has(c)) return false;
            cur = cur.children.get(c)
        }
        return cur.isEnd;
    }

    startsWith(prefix: string): boolean {
        let cur: TrieNode = this.root;
        for(let c of prefix){
            if(!cur.children.has(c)) return false;
            cur = cur.children.get(c)
        }
        return true;
    }
}

Reference