UVa 200

From Algorithmist
Jump to: navigation, search

200 - Rare Order[edit]


An ancient language uses the English letters as alphabets but the ordering of the alphabets is different (i.e. the collating sequence of the language is different). Given a set of strings sorted according to the unknown collating sequence of the language, determine the collating sequence.


Consider a graph whose nodes are the english alphabets and an edge exists between two nodes (u,v) if u precedes v in the collating sequence according to the given strings. Once we have created such a graph, run Warshall's Algorithm to find every such edge to complete the graph. A node which has the least number of incoming edges will be the first letter in the collating sequence, the node with the next minimum incoming edges will be the next letter and so on.

To create the initial edges, compare two consecutive strings and find the first position at which the character (say u) in the first string is different from the character in the second string (say v). Create an edge (u,v) in the graph.

Since it is mentioned that not all letters are necessarily used, but the given list of strings will imply a complete ordering among those letters that are used, a unique answer will always exist.