LeetCode 1804. Implement Trie II (Prefix Tree) in Java

In this post I will solve LeetCode 1804. Implement Trie II (Prefix Tree) problem using Java and the VSCode IDE on a Windows computer.

In a previous post we discussed and implemented a solution for LeetCode 208. Implement Trie (Prefix Tree) in Java which is similar yet different to this one.

Please note that I carried away experimenting with the current problem as I did with the previous one. Due to this I implemented two solutions. After the first one was accepted I tried improving performance and readability. That created a second solution. Due to my approach I ended up with a large amount of code which I will post and comment on. For the first implementation I will go light on comments. Continue reading “LeetCode 1804. Implement Trie II (Prefix Tree) in Java”

LeetCode 208. Implement Trie (Prefix Tree) in Java

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”

Implement Trie (Prefix Tree)

It is Wednesday morning and the cleaning crew is at our place making lots of noise. Typically they show up on Fridays but due to personal issues they requested to move the appointment. They do an excellent job. If you live in the Twin Cities of Minneapolis and St. Paul and are in need of a good cleaning service, please let me know. I will pass your information so you can get in touch with them or vice versa. I value privacy. Continue reading “Implement Trie (Prefix Tree)”

Re-Space

UPDATE – The format for the code for the class TrieNode has been addressed. Sorry for the inconvenience.

It is Friday and my youngest and family will be arriving this afternoon for a weekend long visit. My wife and I are getting ready for their arrival later today. We all enjoy good food so we have an extensive menu planned which includes fugazza, pasta carbonara with lots of pancetta, beef roast with a homemade tomato sauce, limoncello cake and different alcoholic and non-alcoholic beverages.

Let’s get to the main subject of this post. I tackled problem 17.13 from the Cracking the Coding Interview book. The problem is name Re-Space. Continue reading “Re-Space”

No Prefix Set

weekend_on_line_classAs I have mentioned in a previous blog I am currently taking a weekend on-line course on Spring Framework. Last Wednesday my computer received a Windows update labeled “Cumulative Update for Windows 10 Version 1511 for x64-based Systems (KB3185614)”. For some reason the update failed to install on Thursday. After rebooting my machine the installation process continued. A few minutes later it indicated a failure and the system was being restored. The entire process took over one hour. Continue reading “No Prefix Set”

Contacts with Trie

trieHave been somewhat busy in the past couple weeks. To add to it, last weekend I started an on-line “Spring” course. Classes run for three hours Saturdays and Sundays for one month. Need to get the assignments done in the next couple days.

A couple weeks ago I was talking with a manager about prefix searches. At the time I mentioned that I always take a quick look on the Internet to get a general idea on what to do. I did so and Tries came up as an initial candidate. I wrote a blog about it. I tend to be quite passionate with my work and computer science in general. I went and spent some time solving a challenge All Domains -> Data Structures- > Trie -> Contacts on HackerRank (https://www.hackerrank.com/challenges/contacts). Continue reading “Contacts with Trie”