Find the longest common prefix (LCP) between given set of strings

Write an efficient algorithm to find the longest common prefix (LCP) between given set of strings.


 

For example,


Input:  technique, technician, technology, technical
Output: The longest common prefix is techn

 
Input:  techie delight, tech, techie, technology, technical
Output: The longest common prefix is tech

 
Simple solution is to consider each string one at a time, and calculate its longest common prefix with the longest common prefix of strings processed so far. The time complexity of this solution is O(N*M) where N is the number of words, and M is the maximum length of a word.

This is demonstrated below in C++:

 

Download   Run Code

Output:

The longest common prefix is tech

 
We can also use divide and conquer technique for finding the longest common prefix. Like all divide and conquer algorithms, the idea is to divide the group of strings into two smaller sets and then recursively process those sets. This is similar to merge-sort routine except for merging the two halves, we find the longest common prefix of both halves.

 

Download   Run Code

Output:

The longest common prefix is tech

 
The time complexity of above solution is O(N*M) where N is the number of words, and M is the maximum length of a word. The auxiliary space used is O(Mlog(N)) for the call stack.

 
Longest Common Prefix in given set of strings (using Trie)

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of