Medium

Implement Trie (Prefix Tree)

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 very efficient 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.

Examples

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

Output:[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

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.

Hash Map (or Array) Node

Approach

Create a `TrieNode` class. Each node has a hash map (or an array of size 26) representing its children, and a boolean flag `isEndOfWord`. For `insert`, iterate through the characters of the word. If a character is not in the current node's children, add a new `TrieNode`. Then move to the child node. Finally, set `isEndOfWord = true` at the last node. `search` and `startsWith` follow a similar traversal pattern. If a character is missing, return `false`. For `search`, check the `isEndOfWord` flag at the end, while `startsWith` just returns `true` if the traversal finishes successfully.

Complexity Analysis

Time Complexity

O(m) per operation

Space Complexity

O(m * N)

Where m is the length of the word/prefix and N is the number of inserted words.

Solution.java

1class TrieNode {2    TrieNode[] children;3    boolean isEndOfWord;4    5    public TrieNode() {6        children = new TrieNode[26];7        isEndOfWord = false;8    }9}10
11class Trie {12    private TrieNode root;13
14    public Trie() {15        root = new TrieNode();16    }17    18    public void insert(String word) {19        TrieNode curr = root;20        for (char c : word.toCharArray()) {21            int index = c - 'a';22            if (curr.children[index] == null) {23                curr.children[index] = new TrieNode();24            }25            curr = curr.children[index];26        }27        curr.isEndOfWord = true;28    }29    30    public boolean search(String word) {31        TrieNode curr = root;32        for (char c : word.toCharArray()) {33            int index = c - 'a';34            if (curr.children[index] == null) {35                return false;36            }37            curr = curr.children[index];38        }39        return curr.isEndOfWord;40    }41    42    public boolean startsWith(String prefix) {43        TrieNode curr = root;44        for (char c : prefix.toCharArray()) {45            int index = c - 'a';46            if (curr.children[index] == null) {47                return false;48            }49            curr = curr.children[index];50        }51        return true;52    }53}