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

Find Longest Common Prefix (LCP) in given set of strings.


 

For example,


Input:

keys = [“codable”, “code”, “coder”, “coding”]

Output:

Longest Common Prefix is “cod”

 

 
The idea is to use Trie (Prefix Tree). As all descendants of a trie node have a common prefix of the string associated with that node, trie is best data structure for this problem. We start by inserting all keys into trie. Then we traverse the trie until we find a leaf node or node with more than one children. All characters in the trie path forms longest common prefix. For example,

lcp

 
Below is C++ and Java implementation of the idea:

C++

Download   Run Code

Output:

Longest Common Prefix is cod

Java

Download   Run Code

Output:

Longest Common Prefix is cod

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Bharath
Guest
Bharath

There is no need to build a trie. A simpler method would be to take the first word and build a linked list with each character as data in the node.
Then one by one pick the remaining words and iterate through the built linked list, deleting all nodes after the point at which the character in the node and word do not match or, or the word is exhausted, or the linked list is completely traversed.
After doing this for each word, the remaining linked list contains the longest common prefix