Trie (Prefix Tree)

The technique is a tree data structure used to efficiently store and retrieve keys in a dataset of strings.

How to Identify

• Data Structure Involves: Trie, Matrix, String
• Question Type: If the problem requires matching prefixes (with possible complete values).

Example

Implement Trie

Implement a Trie class with insert() and search() functions.

Example

Input:
["Trie", "insert", "search", "search", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"]]
Output:
[null, null, true, false, null, true]

Explanation:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.insert("app");
trie.search("app");     // return True

Typescript

class TrieNode {
    children: Map<string, TrieNode>
    isEndOfWord: boolean

    constructor() {
        this.children = new Map()
        this.isEndOfWord = false
    }
}

class Trie {
    root: TrieNode

    constructor() {
        this.root = new TrieNode()
    }

    insert(word: string): void {
        let current = this.root
        
        for(let i=0; i<word.length; i++){
            if(!current.children.has(word[i])) {
                current.children.set(word[i], new TrieNode())
            }
            current = current.children.get(word[i])! 
        }

        current.isEndOfWord = true
    }

    search(word: string): boolean {
        let current = this.root
        
        for(let i=0; i<word.length; i++){
            if(!current.children.has(word[i])) {
                return false
            }
            current = current.children.get(word[i])!
        }

        return current.isEndOfWord
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 */

Related Problems

	Problems	Difficulty
1	Implement Trie (Prefix Tree)	Medium
2	Add and Search Word	Medium
3	Word Search II	Hard