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”