In the Longest Common Prefix using Trie problem we have given a set of strings, find the longest common prefix. i.e. find the prefix part that is common to all the strings.
Table of Contents
Example
Input1: {“tutorialcup”, “tutorial”, “tussle”, “tumble”}
Output: "tu"
Input2: {"baggage", "banana", "batsmen"}
Output: "ba"
Input3: {"abcd"}
Output: "abcd"
Input4: {"customer","custard"}
Output: "cust"Approach for Longest Common Prefix using Trie
The idea is to use a trie data structure, insert all the given strings into it, traverse the trie, and look for the longest path in the trie without no branching. The characters obtained along such a path is our required longest common prefix.
Algorithm for Longest Common Prefix using Trie
- Construct a trie and insert all the input strings into the trie. insert() function is used to insert an individual string from the given array of strings while constructTrie() is used to insert all the input strings iteratively.
- store the longest common prefix in the prefix variable.
- Now,begin a traversal from root node of the trie and do the following:
- check if the node has single child or not. It has no child or more than one child, terminates the traversal. Counting the number of not null children of a trie node is done using function countChildren().
- If the node has a single child, move on to that child and append character corresponding to that node into the prefix.
- repeat steps 1 and 2 until a node with no child (or more than one child) is found or we reach a trie node that stores the last character of the shortest string in the array of strings. During each step of the traversal, keep adding character corresponding to each trie node traversed.
- The traversal described in step 3 is implemented using function walkTrie(), this function traverses the trie and looks for the longest common prefix path and returns the corresponding longest common prefix.
- In the end, we use a driver function longestCommonPrefix() that combines all the functions mentioned above and returns the longest common prefix among the given array of strings.
C++ Program For Longest Common Prefix using Trie
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* structure of a trie Node */
class TrieNode
{
public:
TrieNode *child[26];
bool isEnd;
TrieNode()
{
for(int i=0;i<26;i++)
child[i] = NULL;
isEnd = false;
}
};
/* inserts a single string into a trie rooted at 'root' */
void insert(TrieNode *root, string key)
{
TrieNode *temp = root;
for(int i=0;i<key.length();i++)
{
int index = int(key[i] - 'a');
if(temp->child[index] == NULL)
temp->child[index] = new TrieNode();
temp = temp->child[index];
}
temp->isEnd = true;
}
/* inserts an array of strings into the trie rooted at 'root' */
void constructTrie(TrieNode *root,vector <string> arr)
{
for(int i=0;i<arr.size();i++)
insert(root,arr[i]);
}
/* counts number of non NULL children a Trie Node has */
int countChildren(TrieNode *root,int &index)
{
int count = 0;
for(int i=0;i<26;i++)
{
if(root->child[i] != NULL)
{
count++;
index = i;
}
}
return count;
}
/* performs traversal on trie of strings rooted at 'root'
and returns the longest common prefix string */
string walkTrie(TrieNode *root)
{
TrieNode *temp = root;
int index;
string prefix;
while (countChildren(temp, index) == 1 && temp->isEnd == false)
{
temp = temp->child[index];
prefix.push_back('a'+index);
}
return prefix;
}
/* combines all the function above and return
LCP among given array of strings */
string longestCommonPrefix(vector <string> arr)
{
TrieNode *root = new TrieNode();
constructTrie(root,arr);
string prefix = walkTrie(root);
return prefix;
}
int main()
{
vector <string> arr = {"tutorialcup", "tutorial", "tussle", "tumble"};
string ans = longestCommonPrefix(arr);
if(ans.length())
cout<<"Longest common prefix = "<<ans<<endl;
else
cout<<"No common prefix found"<<endl;
return 0;
}Longest common prefix = tu
Java Program For Longest Common Prefix using Trie
import java.io.*;
import java.util.*;
class tutorialCup
{
/* structure of a trie Node */
static class TrieNode
{
TrieNode[] child = new TrieNode[26];
boolean isEnd;
public TrieNode()
{
for(int i=0;i<26;i++)
child[i] = null;
isEnd = false;
}
};
/* inserts a single string into a trie rooted at 'root' */
static void insert(TrieNode root, String key)
{
TrieNode temp = root;
for(int i=0;i<key.length();i++)
{
int index = key.charAt(i) - 'a';
if(temp.child[index] == null)
temp.child[index] = new TrieNode();
temp = temp.child[index];
}
temp.isEnd = true;
}
/* inserts an array of strings into the trie rooted at 'root' */
static void constructTrie(TrieNode root,ArrayList <String> arr)
{
for(int i=0;i<arr.size();i++)
insert(root,arr.get(i));
}
static int index;
/* counts number of non NULL children a Trie Node has */
static int countChildren(TrieNode root)
{
int count = 0;
for(int i=0;i<26;i++)
{
if(root.child[i] != null)
{
count++;
index = i;
}
}
return count;
}
/* performs traversal on trie of strings rooted at 'root'
and returns the longest common prefix string */
static StringBuffer walkTrie(TrieNode root)
{
TrieNode temp = root;
StringBuffer prefix = new StringBuffer();
while (countChildren(temp) == 1 && temp.isEnd == false)
{
temp = temp.child[index];
prefix.append((char)('a'+index));
}
return prefix;
}
/* combines all the function above and return
LCP among given array of strings */
static StringBuffer longestCommonPrefix(ArrayList <String> arr)
{
TrieNode root = new TrieNode();
constructTrie(root,arr);
StringBuffer prefix = walkTrie(root);
return prefix;
}
public static void main (String[] args)
{
ArrayList <String> arr = new ArrayList<>(Arrays.asList("tutorialcup", "tutorial", "tussle", "tumble"));
StringBuffer ans = longestCommonPrefix(arr);
if(ans.length() != 0)
System.out.print("Longest common prefix = "+ans);
else
System.out.print("No common prefix found");
}
}Longest common prefix = tu
Complexity Analysis
- Time Complexity : T(n) = O(mn), upper bound of the time taken to construct the trie.
- Space Complexity: A(n) = O(mn), upper bound of space the trie occupies in the memory.
where,
n = length of the longest string
m = number of strings in the string array.