In this post I will solve the LeetCode 208 Implement Trie (Prefix Tree) problem using the Java programming language and the VSCode IDE on a Windows computer. After the code was accepted by LeetCode I decided to add a couple features. The first one is to provide a method to access one of the main uses for a Trie (https://en.wikipedia.org/wiki/Trie). The second, which is based on the first one, is used to display, in order, the words inserted into the Trie.
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.
Constraints:
o 1 <= word.length, prefix.length <= 2000
o word and prefix consist only of lowercase English letters.
o At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.
Related Topics:
o Hash Table
o String
o Design
o Trie
The requirements are very well described. We need to implement the class Trie which must include a specific set of methods. In addition we need to specify the class members. Continue reading “LeetCode 208. Implement Trie (Prefix Tree) in Java”
