Problem explanation
In this problem, we have to find the Longest Common Prefix among all the strings using trie. The Longest Common Prefix is the longest substring that is common in all the strings where the first character of the substring is the first character of the string.
For example in the strings
longest
long
longitude
lonely
The longest common prefix will be “lon”.
Solution
To find the longest common prefix using a trie, we traverse the trie until a it branches. We can check for branch by checking whether two or more characters have pointers to other nodes. If two or more characters in the children array have pointers then we will end the traversal and return the substring formed.
Algorithm
- Start from root and set a variable current as the pointer to the root.
- Initialize the prefix with an empty string.
- Iterate over the trie until current is NULL or EndOfWord is True.
- Iterate over the children array and check how many indexes contain a pointer i.e. don’t contain NULL.
- If count is 1
- append the character of index containing a pointer to the prefix.
- set current to the pointer in the children array.
- else break
- return prefix