Search in a Trie
Explore how to implement and use the search algorithm in a trie data structure. Understand key cases like non-existent words, substring matches, and successful searches. Learn the importance of the isEndWord flag and the traversal logic to verify word presence. This lesson helps you grasp how searching in a trie operates and its 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/letters 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 None 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, but the isEndWord property for it has been set to False.
In the example below, we are searching for the word be. It is a subset of the already existing word bed, but the e node ...