Description

Let’s say we insert the following words in the dictionary: the, a, there, answer, any, by, bye, their, and abc by calling the insertWord() function. Then, by calling the searchWord() function with input, there should return True. Similarly, calling the startsWith() function with the prefix by should also return True.

Solution

Briefly, a trie is a tree of characters. The tree takes a word as a parameter and creates a new node for each character of that word. The node registered for the last character of the word is marked as the end of the word, using a Boolean variable.

To implement the WordDictionary class, we will do the following:

  • Constructor: We will initialize the root node of the tree in the constructor. This node will be of type Node. The Node class contains a dictionary of nodes and the Boolean isWord, which determines if the character is at the end of a word or not.
  • insertWord() function: In this function, we will take in a word as input. Starting from the root node, we will add the word’s characters to the children dictionary of each character as nested dictionaries. We will check if the child node with the character is present or not at each step. If it’s not present, a new node is initialized. For the last character of the word, we also set the isWord to True for the corresponding node.
  • searchWord() function: In this function, we begin checking from the root node to see if the first character exists in children. If it exists, we move on to that node and check its children for the next character. If at any point the node corresponding to a character is not found, we return False. If the whole word is found but isWord is not set to True for the last node, we return False as well. True is only returned if all the characters match and the word also ends at that point.
  • startsWith() function: This function is mostly the same as the searchWord function. The only exception is that we do not check if isWord is also set to True in the last-found node because we are not looking for a complete word, a prefix is enough. In the above trie, for instance, startsWith("th") should return true.

Let’s look at the code for the solution below:

Time complexity

  • searchWord(): The time complexity is O(l), where l is the length of the word that we need to search in the trie.
  • startsWith(): The time complexity is O(l), where l is the length of the prefix that we need to search in the trie.

Space complexity

  • searchWord(): The space complexity is O(1) because constant space is used while searching the trie.
  • startsWith(): The space complexity is O(1) because constant space is used while searching the trie.

Full Stack Programmer, love to solve problem’s during free time.