Theory

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.

To understand with a question:

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, 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

For insertion, we need to consider: 1. we need to insert in a way so that we can search for a word or a prefix in O(logn) time.

For search, we need to consider: 1. For searching words, our data structure needs to capture the end of a word in some way. 2. For searching both prefixes and words, our data structure needs to be able to do so in O(logn) time.

Thus, our data structure needs: 1. A flag to mark the end of a word. 2. A map of current character to subsequent chars.

Thus,

class Node {
    boolean isWordEnd;
    Map<Character, Node> children;
}

TrieNode implementation: TrieNode

Implementation: Trie

Return to Index