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
 
C++ implementation –
 

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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
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

wpDiscuz