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,
Below is C++ and Java implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <unordered_map> #include <string> using namespace std; // A Trie node struct Trie { bool isLeaf; // set when node is a leaf node unordered_map<char, Trie*> character; // Constructor Trie() { isLeaf = false; } }; // Iterative function to insert a string in Trie. void insert(Trie* const &head, string const &str) { // start from root node Trie* curr = head; for (char ch: str) { // create a new node if path doesn't exists if (curr->character.find(ch) == curr->character.end()) { curr->character[ch] = new Trie(); } // go to next node curr = curr->character[ch]; } curr->isLeaf = true; } // Function to find Longest Common Prefix string findLCP(string dict[], int n) { // insert all keys into trie Trie* head = new Trie(); for (int i = 0; i < n; i++) { insert(head, dict[i]); } // traverse the trie and find Longest Common Prefix string lcp; Trie* curr = head; // do till we find a leaf node or node has more than 1 children while (curr && !curr->isLeaf && (curr->character.size() == 1)) { // get iterator to only child auto it = curr->character.begin(); // append current char to LCP lcp += it->first; // update curr pointer to child node curr = it->second; } return lcp; } int main() { // given set of keys string dict[] = { "code", "coder", "coding", "codable", "codec", "codecs", "coded", "codeless", "codependence", "codependency", "codependent", "codependents", "codes", "codesign", "codesigned", "codeveloped", "codeveloper", "codex", "codify", "codiscovered", "codrive" }; // number of keys int n = sizeof(dict)/sizeof(dict[0]); cout << "Longest Common Prefix is " << findLCP(dict, n); return 0; } |
Output:
Longest Common Prefix is cod
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Iterator; import java.util.Map; // A class representing a Trie node class TrieNode { boolean isLeaf = false; // set when node is a leaf node Map<Character, TrieNode> character = new HashMap<>(); }; class LCP { // Iterative function to insert a String in TrieNode private static void insert(TrieNode head, String str) { // start from root node TrieNode curr = head; for (int i = 0; i < str.length(); i++) { // create a new node if path doesn't exists if (!curr.character.containsKey(str.charAt(i))) { curr.character.put(str.charAt(i), new TrieNode()); } // go to next node curr = curr.character.get(str.charAt(i)); } curr.isLeaf = true; } // Function to find Longest Common Prefix public static String findLCP(List<String> dict) { // insert all keys into trie TrieNode head = new TrieNode(); for (String s: dict) { insert(head, s); } // traverse the trie and find Longest Common Prefix StringBuilder lcp = new StringBuilder(); TrieNode curr = head; // do till we find a leaf node or node has more than 1 children while (curr != null && !curr.isLeaf && (curr.character.size() == 1)) { // get iterator to only child Iterator<Map.Entry<Character, TrieNode>> it = curr.character.entrySet().iterator(); if (it.hasNext()) { Map.Entry<Character, TrieNode> entry = it.next(); // append current char to LCP lcp.append(entry.getKey()); // update curr pointer to child node curr = entry.getValue(); } } return lcp.toString(); } public static void main (String[] args) { // given set of keys List<String> dict = Arrays.asList( "code", "coder", "coding", "codable", "codec", "codecs", "coded", "codeless", "codependence", "codependency", "codependent", "codependents", "codes", "codesign", "codesigned", "codeveloped", "codeveloper", "codex", "codify", "codiscovered", "codrive" ); System.out.println("Longest Common Prefix is " + findLCP(dict)); } } |
Output:
Longest Common Prefix is cod
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
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
Can’t get any simpler