How to Find the correct order of alphabets in a given dictionary of ancient origin

Given a dictionary of ancient origin where the words are arranged alphabetically, find the correct order of alphabets in the ancient language.

 
For example,

Input: Ancient dictionary { ¥€±, €±€, €±‰ð, ðß, ±±ð, ±ßß }
Output: The correct order of alphabets in the ancient language are: {¥ € ‰ ð ± ß}
Since the input is small, more than one ordering is possible. Another such ordering is {¥ € ð ± ß ‰}
 
Input: Ancient dictionary { ÿ€±š, €€€ß, €€‰ð, ðß, ±ß¥š }
Output: The correct order of alphabets in the ancient language are: {ÿ € ‰ ð ±}
The alphabets {š, ß, ¥} are not included in the order as they are not properly defined.

 
 
If we carefully analyze the problem, we can see that it is variation of topological sorting of a DAG. A Topological Sorting of a directed acyclic graph is a linear ordering of its vertices such that for every directed edge (u -> v) from vertex u to vertex v, u comes before v in the ordering.
For example, consider the dictionary { ¥€±, €±€, €±‰ð, ðß, ±±ð, ±ßß } of ancient words. For each of the edge (x -> y) shown below, x should appear before y in the final ordering.
¥ --> €
€ --> ð, ‰
± --> ß
ð --> ±
 
If we go a topological sorting on above graph, we get the correct order of alphabets in the ancient language: {¥ € ‰ ð ± ß} or {¥ € ð ± ß ‰}.
 
The idea is to iterate through the complete dictionary and compare adjacent words for a character mismatch. If a mismatch between adjacent words is seen, we insert such pair into a graph. The resultant graph is a DAG since the all words the dictionary are arranged alphabetically. Now since the graph has no directed cycles, we can perform topological sorting on it which gives correct order of alphabets in the ancient language.
 
The algorithm can be implemented as follows in C++:

Output:

The correct order of alphabets in the ancient language are: ¥ € ‰ ð ± ß

 
The time complexity of above solution is O(N*M) where N is the dictionary size and M is the maximum length of a word in the dictionary.


Learn More :