TRIE11 - Editorial

editorial
, ,
1

Problem Link - Auto-Complete

Problem Statement:

Complete the function autocomplete to print print all the words in the trie that start with a string S. The string S is passed as an argument in the function

Approach:

The key idea of this solution is to use a Trie (pronounced as “try”), which is a specialized tree-like data structure used for storing a dynamic set of strings. Each node in the Trie represents a character of a word, and it allows for efficient insertion and search operations.

  1. TrieNode Structure:

    • Each TrieNode has an array of pointers (children) to its child nodes, representing the next characters in the words.

    • A boolean flag (isEndOfWord) indicates if the node marks the end of a valid word.

  2. Trie Class: insert(const string& word)

    • This function inserts a word into the Trie by iterating through each character of the word.

    • For each character, it checks if the corresponding child node exists; if not, it creates a new node.

    • Once all characters of the word are processed, it marks the last node as the end of a word.

  3. search(const string& word):

    • This function searches for a word in the Trie by checking if the characters exist in sequence.

    • It returns true if the word exists in the Trie and is marked as an end of a word.

  4. Main Function:

    • First, it reads a number of words to be inserted into the Trie.

    • It then reads words to be searched and prints “correct” if found and “incorrect” otherwise.

This logic makes the Trie a powerful tool for prefix-based search problems and ensures efficient lookup times.

Time Complexity:

  • Insertion: O(m) where m is the length of the word being inserted.

  • Search: O(m) where m is the length of the word being searched.

Space Complexity:

  • O(n * m) where n is the number of words and m is the average length of the words, as each word can create up to m nodes in the Trie.