Let us assume that we have a list of words found in the dictionary in the same order as given: [“baa”, “abcd”, “abca”, “cab”, “cad”] Now, ninja needs to find the order of the characters used in these strings. The order would be: ‘b’, ‘d’, ‘a’, ‘c’, because “baa” comes before “abcd”, hence ‘b’ will come before ‘a’ in the order, similarly because, “abcd” comes before “abca”, ‘d’ will come before ‘a’. And so on.
A certain list of words might have more than one correct order of characters. In such cases, you need to find the smallest in normal lexicographical order. In the case of INVALID ORDER, simply return an empty string.
words = [“aba”, “bba”, “aaa”]. In this case, no valid order is possible because, from the first two words, we can deduce ‘a’ should appear before ‘b’, but from the last two words, we can deduce ‘b’ should appear before ‘a’ which is not possible.
words = [“ca”, “cb”]. In this case, we only know that ‘b’ will come after ‘a’ in the order of characters, but we don't have any knowledge of ‘c’. So, the valid correct orders can be = “abc”, “cab”, “acb”. Out of these, “abc” is lexicographically smallest, hence it will be printed.
The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case will contain an integer ‘N’, which denotes the number of words in the dictionary. The second line of each test case will contain ‘N’ space-separated strings which denote the words of the dictionary.
For each test case, print the order of characters. Output for every test case will be printed in a separate line.
1 <= T <= 10 1 <= N <= 300 0 <= size <= 100 Time limit: 1 sec
The idea behind this approach is to create a graph of the words of the dictionary and then apply the topological ordering of the graph.
A topological ordering of a directed 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.
The approach is to take two words from the array of words and then compare characters of both words and find the first character that is not the same in the words.
Then, create an edge in the graph from the first different character of the first word to the second word.
Finally, apply topological sorting in the above-created graph.
Let us understand this better by dividing the complete solution into two parts:
Algorithm + Pseudo Code:
Keep in mind the following cases: