Longest word in dictionary

Method 2: Trie with Depth-First Search

A prefix can store all the possible prefixes in a prefix tree. Consider the word “work”. The prefix tree for “work” will look like the figure given below.

Let’s insert other words from ‘WORDLIST’ in the prefix tree. The resulting tree is given below.

Prefix trees are stored using a trie. Additional information like the end of the word and index of the word is stored in a trie.

Structure of Trie Node

Structure the trie node according to the data required from each node of the trie. Every trie node must contain two data members: ‘INDEX’ and ‘NEXT’.

• ‘INDEX’ is an integer. It represents the index of the word(created from root to the current trie) in the ‘WORDLIST’. For a node that is not an end of any word, ‘INDEX’ is set to -1.
• ‘NEXT’ is a hashmap. It stores the address of a trie node corresponding to a character.

Insert all the words in the trie structure. A depth-first search can look for the longest prefix possible. 

Functional Requirements

To use a DFS Algorithm on a trie structure, we require INSERT() and DFS(). Let’s describe these functions and their algorithms.

• INSERT(): INSERT() function inserts the words with their indices in the trie. For an INSERT() function, two arguments are required: word and index. Start with the ‘ROOT ’ of the trie as ‘CURRENT_NODE’. Iterate through all the letters of the word. If the current character’s ‘NEXT’ pointer is not pointing to a trie node, create one. Otherwise, move the pointer to the ‘CURRENT_NODE’ to the ‘NEXT’ pointer. At the end of the word, the ‘CURRENT_NODE’ should have the ‘INDEX’of the word inserted.
   

Algorithm

• Set ‘CURRENT_NODE’ equal to ‘ROOT’.
• Iterate the ‘LETTER’ variable from beginning to end of the word and perform the following operations:
  • If CURRENT_NODE -> NEXT[LETTER] is pointing to NULL, then:
    • Create a node at CURRENT_NODE -> NEXT[LETTER].
  • Set ‘CURRENT_NODE’ equal to CURRENT_NODE -> NEXT[LETTER].
• Set CURRENT_NODE->INDEX equal to ‘INDEX’ (‘INDEX’ represents the index of the current word).

• DFS():  The DFS() function does a depth-first search on the trie. For every current node(‘CURRENT_NODE’ ) in our method, we store its next possible characters(CURRENT_NODE.NEXT) in a stack.

Every node has an index(CURRENT_NODE.INDEX), representing the index of the word containing characters from ‘ROOT’ to ‘CURRENT_NODE’. If the word is longest and lexicographically smallest discovered so far, consider it an answer(‘ANSWER’) for the path traveled so far. Consider the top node(‘TOP_NODE’) of the stack as the new current node(CURRENT_NODE.NEXT) and repeat the process.
 

Algorithm

• Initialize the ‘ANSWER’ variable as an empty string.
• Initialize a stack ‘CURRENT_STACK’ with root(‘ROOT’) of the trie(to store all the next nodes to the current node).
• While ‘CURRENT_STACK’ is not empty, do:
  • Set ‘CURRENT_NODE’ as the top element of the ‘CURRENT_STACK’ (to do dfs on the ‘CURRENT_NODE’ ).

Program

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;

// Creating a Node class to store Nodes of a trie.
class Node
{

  public:

  // 'NEXT' stores the address of a node corresponding to a character.
  unordered_map<char, Node *> next;

  // 'INDEX' represents the index of the word.
  int index;

  // Constructor to create a node with index as -1.
  Node()
  {
    index = -1;
  }
};

// Creating a Trie class to create a trie data structure.
class Trie
{

  // 'ROOT' refers to the root node of the trie.
  Node *root;

  // 'WORDLIST' is stored as data member for lookup in dfs function.
  vector<string> wordlist;

  /* 'INSERT' function to store all the words 
      and their indices in the trie data structure. */
  void insert(string word, int index)
  {

    // Set 'CURRENT_NODE' equal to 'ROOT'.
    Node *currentNode = root;

    /* Iterate the 'LETTER' variable from beginning to end of the word
       to insert all the letters of word in the trie. */
    for (char letter : word)
    {

      // If character node is not present in the trie, create one.
      if (currentNode->next[letter] == NULL)
      {
        currentNode->next[letter] = new Node();
      }

      // Move 'CURRENT_NODE' to next letter.
      currentNode = currentNode->next[letter];
    }

    // Set index of word at the last letter node.
    currentNode->index = index;
  }

  public:
  // Constructor for a trie data structure to fill it with given input.
  Trie(vector<string> wordlist)
  {

    // Set 'ROOT' pointer pointing to this trie.
    this->root = new Node();

    // Store 'WORDLIST' in trie for lookup in dfs.
    this->wordlist = wordlist;

    // 'LENGTH' represents number of words in the 'WORDLIST'.
    int length = wordlist.size();

    // Iterate through 'WORDLIST'.
    for (int index = 0; index < length; index++)
    {

      // Insert current word and its index in trie.
      insert(wordlist[index], index);
    }
  }

  string dfs()
  {

    // Stack to store all the next nodes to the current node.
    stack<Node *> currentStack;

    // Initializing root of this trie in the stack.
    currentStack.push(root);

    /* Initialize the 'ANSWER' variable as an empty string. 
       This represents the final answer to be returned. */
    string answer = "";

    // 'CURRENT_WORD' represents the current word in the 'WORDLIST' dfs state refers to.
    string currentWord;
    while (!currentStack.empty())
    {

      // 'CURRENT_NODE' represents the node that is being explored for dfs.
      Node *currentNode = currentStack.top();

      // As 'CURRENT_NODE' is being explored, remove it from the stack.
      currentStack.pop();

      /* CURRENT_NODE index is -1 means this word is not present in
         'WORDLIST'. So, it should not be explored for dfs.
        For  CURRENT_NODE = 'ROOT', 
         we need to explore it's next nodes.*/
      if (currentNode->index != -1 || currentNode == root)
      {

        // If 'CURRENT_NODE' is root then it should not be considered for answer.
        if (currentNode != root)
          currentWord = wordlist[currentNode->index];

        /* If current word is bigger than the answer discovered so far,
           it can be the new answer. If both the lengths are equal,
           we should set current word as answer 
           if it is lexicographically smaller. */
        if (currentWord.length() > answer.length())
          answer = currentWord;
        else if (currentWord.length() == answer.length() && currentWord < answer)
        {
          answer = currentWord;
        }

        // Exploring next nodes of 'CURRENT_NODE'.
        for (auto nextNode : currentNode->next)
        {
          currentStack.push(nextNode.second);
        }
      }
    }
    return answer;
  }
};
int main()
{

  int numWords;
  cout << "Enter number of words: ";
  cin >> numWords;

  // 'WORDLIST' vector to store all the words as input.
  vector<string> wordlist(numWords);

  cout << "Enter words:\n";
  for (int i = 0; i < numWords; i++)
  {
    cin >> wordlist[i];
  }

  // Creating a new trie with given 'WORDLIST'.
  Trie *currentTrie = new Trie(wordlist);

  cout << "Longest word in dictionary: ";
  cout << currentTrie->dfs();
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter number of words: 6
w   wo   wor   wow   worm   work

Output

Longest word in dictionary: work 

Complexity Analysis

Time Complexity: In the worst case, we may need to traverse through the whole trie data structure. The trie data structure contains all the letters of al the words. So, the time complexity of this method is O(⅀W_i), where W_i represents the length of the ith word in ‘WORDLIST’.

Space Complexity: An additional space is required to store all the  words in the trie data structure. So, the space complexity is O(⅀W_i), where W_i represents the length of the ith word in ‘WORDLIST’.

Key Takeaways

Congratulations! You have successfully learned to find the longest word in dictionary efficiently. Learning something new is never easy. Practicing what you’ve learned is even more difficult. But, a good coder never gives up. So, head over to our practice platform Coding Ninjas Studio to practice top problems and many more. Coding Ninjas Studio also offers interesting interview experiences and blogs like this. So keep learning and Happy Coding!