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

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


For example,


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


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,


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


Download   Run Code


Longest Common Prefix is cod


Download   Run Code


Longest Common Prefix is cod

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


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

newest oldest most voted
Notify of

Can’t get any simpler


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