Implement Trie (Prefix Tree)
The key idea
Store words as a tree of characters where every node has up to 26 children, one per letter. A boolean
isEnd flag on a node marks where a full word terminates — that flag is the only difference between search (must land on a node with isEnd set) and startsWith (only needs the path to exist).Problem
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a set 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.
Constraints
1 <= word.length, prefix.length <= 2000wordandprefixconsist only of lowercase English letters.- At most
3 * 10^4calls in total will be made toinsert,search, andstartsWith.
Examples
Input: ["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output: [null,null,true,false,true,null,true]
Complexity
Time: O(L) Space: O(N*L)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization