Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction-  
2.
Solution Approach
3.
Algorithm -
4.
C++ code:
5.
Algorithm Complexity: 
6.
FAQs
7.
Key takeaways-
Last Updated: Mar 27, 2024

Longest Common Prefix Using Trie

Author Riya
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction-  

This blog will discuss how to find the longest common prefix using trie. In this problem, we will be given an 'N' number of words, i.e., strings, and we have to find the longest common prefix using trie.

The longest common prefix of a set of strings is the longest string which occurs at the beginning of each string.


Let’s understand the problem with the following example:

Suppose N = 4 

And, the given strings are :

words = {“coding”, "coder", "codestudio", "code"}


We can see that "cod" is the longest common prefix in these four strings. And, we have to find this longest common prefix using trie.

Now, we have understood the problem, we will discuss the approach using trie in the next section.
 

Solution Approach

This section will discuss the approach to find the longest common prefix using trie. The approach is simply based on the trie data structure. We have been given 'N' number of strings, so we will first insert all these strings into a trie. After inserting all the strings, we will start traversing the tree from its root node and continue traversal until we either find a node with more than one branch or a node with zero branches. We are stopping the traversal on a node with more than one branch because more than one string will originate from this node, so the further nodes won't be a part of a common prefix. And, we are stopping on a node having zero branches because at this node, one of the strings will end, and so further, we can't find a common prefix.

 

Let's have a look at the trie formed by the strings of the example taken in the previous section and understand this approach of finding the longest common prefix using trie.
 

In this trie formed by the strings of our example, we can see that the string formed by the node starting from the root node to the last node, which is not having more than one branch, will be the longest common prefix.  Here, "cod" will be the longest common prefix.

                     

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm -

Step 1. Create a class "Node", which will be used for creating the trie class. The "Node" class will have the following members:

  1. branches[]: An array of Nodes having size 26, which will be used to store the pointers to the nodes linked with a character from this node. Please note here that we are assuming that the strings can contain only 26 lowercase letters, so we have taken the maximum size as 26.
  2. flag: A boolean variable to keep track of whether a string is ending at the node or not
  3. Node(): A constructor for this class, which will initialize all the values of the "branches" array as NULL and the "flag" variable as false.
  4. countBranches(): A function to return the number of non-null branches of the node. 
  5. containsKey(): A function to check whether a branch exists in the node for the given character
  6. addBranch(): A function to add a branch at the given character
  7. setEnd(): A function to mark the node as the end of a string by setting the "flag" variable is true.

 

Step 2. Create a class "Trie" to implement the trie, which will have the following members:

  1. root: The pointer to the root node of the trie 
  2. Trie(): A constructor for the class that will initialize the root node of the trie.
  3. insert(): A function that will take a string as input and insert that string into the trie.

 

Step 3.  Now create a function "findCommonPrefix()" to find the longest common prefix using trie. It will take two inputs - vector of strings and size of the vector. Inside the function, create a new trie using the "Trie()" constructor. Then insert all the strings one by one using the "insert()" function of the "Trie" class.

Step 4.  After inserting all the strings, start traversing the trie using a variable "curr_node" and a "while" loop. Initialize a variable "longestCommonPrefix" outside the "while" loop and keep adding the characters inside the "while" loop. Stop the "while" loop when a node is reached which has more than one branch of which is the end of a string.

Step 5. Finally, return the variable "longestCommonPrefix", which will be the longest common prefix of the given strings.

 

C++ code:

// C++ program to find the longest common prefix using trie
#include<bits/stdc++.h>
using namespace std;



// Class used for creating the nodes of trie data structure
class Node
{
Public:


// Each node will have an array of nodes which can contain maximum 26 branches linked to each node
Node* branches[26];

// A boolean variable to mark whether it is the end of a string or not
bool flag;

// Constructor for the Node class
Node() {

// Initially all the branches will have NULL value
for(int i=0; i<26; i++)
  {
   branches[i] = NULL;
  }
  
// Initially, the flag will be false, denoting that the current node is not the end of any string
flag=false;
}

// Function to count the number of branches, a node of the trie is having
int countBranches() {
int count = 0;
for(int i=0; i<26; i++)
  {
   if(branches[i] != NULL) {
     count++;
   }
  }
return count;
}

// Function to check whether the node has a branch with the given character
bool containsKey(char ch) {
if(branches[ch - 'a'] != NULL) {
return true;
}
else {
return false;
}
}

// Function to add a branch in the node with the given character
void addBranch(char ch, Node* node) {
branches[ch - 'a'] = node;
}

// Function to return the node which is linked to the node at the given character
Node* get(char ch) {
return branches[ch - 'a'];
}

// Function to set the node as the end of a string by making the variable flag as true
void setEnd() {
flag = true;
}
};


// Trie class
class Trie {

public:
  // Root of the trie
  Node* root;


       // Constructor for the trie class
  Trie() {
     root = new Node();
  }
   
  // Function to insert a string into the trie
  void insert(string word) {
     Node* curr_node = root;
     for(int i = 0; i < word.length(); i++)
       {
        if(!curr_node->containsKey(word[i])) {
        curr_node->addBranch(word[i], new Node());
        }
       
        curr_node = curr_node->get(word[i]);
       }
     curr_node->setEnd();
  }
 
};


// Function to find the longest common prefix using trie
string findCommonPrefix(vector<string> words, int N)
{
// First create a trie and insert all the strings into it
Trie* trie = new Trie();

for(int i=0; i<N; i++)
  {
   trie->insert(words[i]);
  }

// string variable to store the longest common prefix
string longestCommonPrefix;

// variable to keep track of current node while traversing the trie
Node* curr_node = trie->root;

// Traverse the trie created above until we reach either a node having more than one branch or a node which is the end of a string
while(curr_node->countBranches() == 1 && curr_node->flag == false)
  {


   // Find the character in the node which is having a Not Null branch
   for(int i=0; i<26; i++)
     {
      if(curr_node->branches[i] != NULL) {


        // Add that character into the longestCommonPrefix string
        longestCommonPrefix.push_back('a' + i);


        // Move to the next node
        curr_node = curr_node->get('a' + i);
        break;
      }
     }
  }
 
// Return the longest common prefix 
return longestCommonPrefix;

}


// Main Function
int main()
{
// Number of strings
int N = 4;

// Given vector of words, for which we have to find the longest common prefix using trie
vector<string> words;
words.push_back("coding");
words.push_back("coder");
words.push_back("Coding Ninjas Studio");
words.push_back("code");


    // Calling the function to find the longest common prefix using trie
string commonPrefix = findCommonPrefix(words, 4);

if(commonPrefix.length()>0) {
cout<<"The common prefix in the given strings is: "<<commonPrefix;
}
else {
cout<<"There is no common prefix in the given strings";
}

return 0;



}

 

Output:
The common prefix in the given strings is: cod

 

Algorithm Complexity: 

Time Complexity: O(N * M)

In the function "findCommonPrefix()" to find the longest common refix using trie, inserting all the strings into the trie will take O(N * M) time, and traversing the trie will take O(M) time, so the overall time complexity will be O(N * M), where 'N' is the number of strings and 'M' is the length of the longest string.

Space Complexity: O(26 * N * M) 

In the function "findCommonPrefix()" to find the longest common refix using trie, a trie is created, and all the strings are inserted into it, so the space complexity will be O(26 * N * M), where 'N' is the number of strings and 'M' is the length of the longest string.

 

FAQs

  1. What is the time complexity of inserting a string into a trie?
    The time complexity of inserting a string into a trie is O(N), where ‘N’ is the length of the string which is being inserted.
     
  2. What is the time complexity of searching a string into a trie??
    The time complexity of searching a string into a trie is O(N), where ‘N’ is the length of the string which is being searched.

 

Key takeaways-

This article discussed how to find the longest common prefix using trie, its C++ implementation, and its time and space complexity. If you want to solve more problems on trie data structure for practice, you can visit Coding Ninjas Studio.

Check out this problem - Longest Common Prefix


If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

 

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Container With Most Water
Next article
Aho-corasick Algorithm
Live masterclass