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
wpDiscuz