Search in a Trie
Understand how to implement and perform search operations in a trie data structure. This lesson covers cases for nonexistent words, substrings, and complete words, explaining the importance of the endOfWord flag and the search algorithm's time complexity.
We'll cover the following...
Search Algorithm #
If we want to check whether a word is present in the trie or not, we just need to keep tracing the path in the trie corresponding to the characters in the word.
The logic isn’t too complex, but there are a few cases we need to take care of.
Case 1: Non-Existent Word #
If we are searching for a word that doesn’t exist in the trie and is not a subset of any other word, by principle, we will find null before the last character of the word can be found.
For a better understanding, check out the illustration below:
Case 2: Word Exists as a Substring #
This is the case where our word can be found as a substring of another word, ...