Task description: A (pronounced as “try”) or 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. trie prefix tree Implement the Trie class: Initializes the trie object. Trie() Inserts the string into the trie. void insert(String word) word Returns if the string is in the trie (i.e., was inserted before), and otherwise. boolean search(String word) true word false Returns if there is a previously inserted string that has the prefix , and otherwise. boolean startsWith(String prefix) true word prefix false Example 1: Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true] Explanation
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 and consist only of lowercase English letters. word prefix At most calls will be made to , , and . 3 * 10^4 in total insert search startsWith Reasoning: is the classic data structure that is widely used. One of the most famous uses is text searching. Let’s take Google.com as an example. Trie Google’s example Have you ever noticed whenever you start typing a search phrase to a search bar you almost immediately get some suggestion from the searching system? I bet the answer is “Yes”. The Trie data structure makes it possible. Let’s add some words to Trie and see how it looks like this: Example of Trie with some words The Trie above contains words: Algorithm, Animation, Ant, Apache, Append, Apple, Application, Apricot. As you may notice we treat every word as a sequence of characters. Starting from the first character of each word we attach it to the root of the and move down till we reach the last character of each word. Trie Once we reached the end of a word we mark that last as the end of the word. I hope now it’s clear to you how it works in general. If you still struggle with it, I recommend you to read . Node Wikipedia’s article Solution: We are to implement Trie with the following method: https://gist.github.com/RakhmedovRS/a53ea510ad97088fdfd4829209d405b2 As we saw in the example of real we had to notice that as with any other data structure it consists of smaller pieces which are usually called . Let’s introduce this small part: Trie Tree Node https://gist.github.com/RakhmedovRS/bb2a188cd156565b692af1f5262d96a3 A few things we need to have a closer look at here: We have the boolean array which will tell us if we have particular characters in a particular node. boolean variable which answers just one question, whether or not the current node is the end of a word in our Trie. Last but not least TrieNode array stores child TrieNodes of the current TrieNode. chars isEnd children Let’s look at other methods, one by one: Method returns nothing and accepts word to insert into the Trie: void insert(String word) https://gist.github.com/RakhmedovRS/b460db4fd040a47ca33e8afc401af7c0 Starting from the root of the Trie we iterate through every char in provided word and create a new TrieNode every time if we don’t have one. At the last character in word, we mark TrieNode as isEnd. The next method in our list is which searches for a particular word in the Trie and returns a boolean value depending on whether or not the Trie contains it. As input, it takes a word. boolean search(String word) https://gist.github.com/RakhmedovRS/18bb68c4e83f3c602afa4a338e96fbc2 Here we do the same as in the previous method except for a few things. Iterate through every character in provided word and if we don’t have a child with the next character we return false. At the end of a word, we return the current node value of . isEnd Lastly method takes prefix and returns true if we have a prefix in our Trie if not we return false. boolean startsWith(String prefix) https://gist.github.com/RakhmedovRS/d25842ef37c339e6260ef50097713e84 This method does completely the same as the previous one except for only one thing. If we managed to iterate through the whole prefix we return true, because we’re looking for the prefix and not an entire word, otherwise we return false. As always at the end of the article, I prove the full source code of the problem https://gist.github.com/RakhmedovRS/cff7b0ea83d0a598c86c7b9aac834425 It has linear time and space complexity and has the following position among other people's solutions. Also published . here

Apache

Apple

Google

How To Merge Two Sorted Lists

Implementing a Singly or Doubly Linked List in Java (A LeetCode Question)

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Too Long; Didn't Read

How to Implement Trie (Prefix Tree) - Blind 75 LeetCode Questions

How to Implement Trie (Prefix Tree) - Blind 75 LeetCode Questions

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Clone Graph Blind75 LeetCode Problem

A Hacker's Guide to Competitive Programming

30 Days DSA Interview Preparation Plan

7 Essential Tips for Competitive Programming and DSA

Binary Lifting and Its Applications

Clone Graph Blind75 LeetCode Problem

A Hacker's Guide to Competitive Programming

30 Days DSA Interview Preparation Plan

7 Essential Tips for Competitive Programming and DSA

Binary Lifting and Its Applications

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps