Have you ever heard about the alien dictionary?
Well, if you haven’t, you are missing out on a very important coding problem! Alien language also consists of English letters in lowercase. However, these letters are present in a unique or different order. In an alien language, this order of all alphabets is found by the permutation of the lowercase alphabets. Questions based on the alien language are generally asked in coding interviews especially when you are appearing for advanced job interviews. One such question that you will encounter is the alien dictionary problem. If you are not aware of what the problem is, we have got you covered. Read everything that you need to know about the problem here.
The Problem Statement
You will be provided with a sorted dictionary written in an alien language containing N number of words and K beginning alphabets present in the English dictionary. Here, you are required to find the order in which the alien dictionary characters will appear. To simplify it, you will be given certain strings written in an alien language in the same sorted order as they will generally appear in the alien dictionary.
Now, you will have to check all these strings properly and then determine the exact order of characters in which they are used in the alien dictionary.
To understand the problem better, consider the following example: You are given the following dictionary order= {“baa”, “abcd”. “Abca”, “cab”, “cad”} Here, the output will be BDAC.
Explanation:
To begin with, you will have to compare the initial two strings. The first letters of these strings are different from each other. Therefore, we have concluded that A is the successor of B in an alien dictionary. Other than that, we will not use any other letter from these strings. Now, we will compare the next two strings and you will observe that abc is present in both of them. Here, in these strings, d and vary and this is why we have concluded A is the successor of D. Similarly, we have made other assumptions like A is present before C and D is the successor of B. This is why we have come to the conclusion that the order of characters in an alien dictionary will be B D A C
The Optimal Solution For Alien Dictionary Problem
To resolve the Alien dictionary problem, we use the Topological sorting method. To begin with, we will first compare the strings and find dependencies in these characters. We need to represent the dependencies with the help of a directed graph in which the edges will also appear in the way the characters are used in alien dictionaries. After creating the directed graph, we need to apply topological sort on this graph in order to find the character order. For this, we have to perform the following operations:
To begin with, iterate the vector of strings provided and then compare the consecutive strings letter by letter. When there is a mismatch observed in the strings, you will have to add the edge to your graph directed from the letter present U string to the letter present in the V string.
Now that your acyclic graph is ready, you will have to perform topological sorting to it and determine the character order.
If you are not aware of how to perform Topological sorting, let’s understand what it is and how it works!
Understanding Topological Sorting
The topological sort is defined as the upright ordering of the vertices of the directed acyclic graph in such a way that for every edge directed from u to v, the vertex u will come before v in the order....
Comments