Share the joy
This is a very interesting question from geeksforgeek. link
Problem: Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.
Example
Input: words[] = {“baa”, “abcd”, “abca”, “cab”, “cad”}
Output: Order of characters is ‘b’, ‘d’, ‘a’, ‘c’ Note that words are sorted and in the given language “baa” comes before “abcd”, therefore ‘b’ is before ‘a’ in output. Similarly we can find other orders.
Solution:
For “baa”, “abcd”, “abca”, “cab”, “cad”, we can conclude: b->a, a->c
For “abcd”, “abca”, we can conclude: d->a
For “cab”, “cad”, we can conclude: b->d
Then do topological sorting on it.