Easy as CAB
Jump to navigation
Jump to search
This problem asks us to generate a sorted alphabet based on a list of sorted words in that alphabet.
We see that each pair of words will give us exactly one letter "relationship." Whatever position the two words first differ at will imply that the differing character in the second word is greater lexicographically than the one in the first.
We generate all these relationships, then we can simply run topological sort against the graph to produce the alphabet.
The problem is intractable if there is any ambiguity in the topological sort: namely, if there is ever more than a single word in the queue at a time.