Longest Common Prefix Using Trie

// 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;



}

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

Run Code

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

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

Run Code