Do you think IIT Guwahati certified course can help you in your career?
Introduction
Graphs form the backbone of any coding interview. Thus it's very important to have a good grasp of this topic. But don't you worry about any of it. Ninjas are here for you, and today we will be going to the famous interview questions ‘Alien Dictionary’. The alien dictionary question revolves around the concept of topological sorting. So now, let's take a look at the problem statement of the question ‘The Alien Dictionary.’
Understanding the Problem
A sorted (lexical order) dictionary of an alien language has been given to you(Alien Dictionary). Your task is to find the alien language's character order. This dictionary will be provided to you as an array of strings named 'dictionary,' with a size of 'N.
Example:
Input
Alien Dictionary= ["caa," "aaa," "aab"]
Output
[c,a,b]
Explanation:
We can see that c comes before a in the dictionary so [c, a], then we see that b comes after a; thus the order becomes [c, a,b].
Permutation Approach
Find all of the distinct characters that appear in each word.
Produce all possible combinations of these distinct characters.
Each permutation should be treated as a valid alphabetical sequence. Check to see if the given words are sorted in this order. To accomplish this, we will:-
Let the current word be 'currWord' and the next word be 'nextWord' for all words from 1 to n - 1.
Compare the characters of both words one by one to find the first mismatching character. We move on to the next word if there was no mismatching character.
Let's say the mismatched characters in 'currWord' and 'nextWord' were 'ch1' and 'ch2', respectively.
If these words (currWord and nextWord) follow the dictionary, 'ch1' will appear in the sequence before 'ch2.'
If the words are sorted in the current sequence, we will return the current sequence.
Code
#include<bits/stdc++.h>
using namespace std;
bool isOrderValid(string *dictionary, int n, vector<char> &permutation)
{
unordered_map<char, int> pos;
for (int i = 0; i < permutation.size(); i++)
{
if (pos.find(permutation[i]) == pos.end())
{
pos[permutation[i]] = i;
}
}
for (int i = 0; i < n - 1; i++)
{
string currWord = dictionary[i];
string nextWord = dictionary[i + 1];
for (int j = 0; j < min(currWord.length(), nextWord.length()); j++)
{
if (currWord[j] != nextWord[j])
{
if (pos.find(currWord[j]) == pos.end() || pos.find(nextWord[j]) == pos.end() ||
pos[nextWord[j]] < pos[currWord[j]])
{
return false;
}
else
{
break;
}
}
}
if (currWord.length() > nextWord.length())
{
return false;
}
}
return true;
}
vector<char> getAlienLanguage(string *dictionary, int n)
{
vector<char> permutation;
unordered_set<char> uniqChar;
for (int i = 0; i < n; ++i)
{
for (char c : dictionary[i])
{
if (uniqChar.find(c) == uniqChar.end())
{
permutation.push_back(c);
}
uniqChar.insert(c);
}
}
sort(permutation.begin(), permutation.end());
do
{
if (isOrderValid(dictionary, n, permutation))
{
return permutation;
}
} while (next_permutation(permutation.begin(), permutation.end()));
return permutation;
}
int main() {
int n;
cin>>n;
string *dictionary=new string[n];
for(int i=0;i<n;i++)
cin>>dictionary[i];
vector<char>ans=getAlienLanguage(dictionary,n);
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<" ";
return 0;
}
You can also try this code with Online C++ Compiler
O(K! * N * L), where K is the number of distinct characters, N is the number of words in the dictionary, and L is the maximum length of a word in the dictionary.
Explanation: This is because we generate all possible permutations which cost K! operations for each word in the dictionary leading to a complexity of K! * N. Also, for each permutation, we compare L characters which give us an overall time complexity of K! * N * L.
O(K), where K is the number of distinct characters
Explanation: Since we are storing K distinct characters
Topological Sort Approach
If we consider the first two words of the alien dictionary ["wrt", "wrf",....], then looking at the first mismatch in the characters tells us crucial information about the order they occur!
That is, we can say that 't' comes before 'f' in the above two words! We can denote this relation by, ‘t’ → ‘f’.
A directed graph can be used to represent this relationship!
Hence,
Make a graph representing the above relationship by iterating over all of the words. The graph's vertices will be all of the distinct characters, while the directed edge will be the relation, mapping which character comes before another.
Return one of the possible orders for the same by performing a Topological Sort on the built graph.
Code
#include<bits/stdc++.h>
using namespace std;
class Graph
{
public:
vector<vector<int>> neighbours;
int numVertices;
Graph(int vertexCount)
{
numVertices = vertexCount;
neighbours.resize(vertexCount);
}
void addEdge(int src, int dest)
{
neighbours[src].push_back(dest);
}
vector<char> topologicalSort()
{
vector<bool> visited(numVertices, false);
stack<int> completedVertices;
// Getting the topological sort
for (int i = 0; i < numVertices; i++)
{
if (!visited[i])
{
dfs(i, visited, completedVertices);
}
}
// Storing the topological sort in a character array
vector<char> arr(completedVertices.size());
int curr = 0;
while (!completedVertices.empty())
{
arr[curr++] = ((char)('a' + completedVertices.top()));
completedVertices.pop();
}
return arr;
}
void dfs(int curr, vector<bool> &visited, stack<int> &completedVertices)
{
// Mark the current node as visited.
visited[curr] = true;
// Make a recursive call to all the neighbours.
for (int neighnour : neighbours[curr])
{
if (!visited[neighnour])
{
dfs(neighnour, visited, completedVertices);
}
}
// All neighbours completed.
completedVertices.push(curr);
}
};
vector<char> getAlienLanguage(string *dictionary, int n)
{
// Find the number of unique characters in the strings.
unordered_set<char> uniqChars;
for (int i = 0; i < n; ++i)
{
for (char c : dictionary[i])
{
uniqChars.insert(c);
}
}
Graph *graph = new Graph(uniqChars.size());
for (int i = 0; i < n - 1; i++)
{
string currWord = dictionary[i];
string nextWord = dictionary[i + 1];
int compareTill = min(currWord.length(), nextWord.length());
for (int j = 0; j < compareTill; j++)
{
if (nextWord[j] != currWord[j])
{
graph->addEdge(currWord[j] - 'a', nextWord[j] - 'a');
break;
}
}
}
return graph->topologicalSort();
}
int main() {
int n;
cin>>n;
string *dictionary=new string[n];
for(int i=0;i<n;i++)
cin>>dictionary[i];
vector<char>ans=getAlienLanguage(dictionary,n);
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<" ";
return 0;
}
You can also try this code with Online C++ Compiler
O(N + K), Where N is the total number of words and K is the total number of unique characters present in the list of N words.
Explanation: The time complexity of the Topological Sort is O(V + E), where V is the number of vertices and E is the number of edges, which is O(K + N).
Space Complexity
O(K), where K is the number of distinct characters.
Explanation: Since we are storing K distinct characters
To know about the concept and implementation of code you should watch this video to understand it better.
Frequently asked questions
What is a Graph? A graph is a non-linear data structure made up of nodes and edges. The edges represent some correlation between the nodes. Nodes are sometimes known as vertices, while edges are lines or arcs that connect any two nodes in the network.
How do directed and undirected graphs differ? The directed graph contains ordered pairs of vertices, while the undirected contains unordered pairs of vertices. In a directed graph, edges represent the direction Of vertices, while edges do not represent the direction of vertices.
What is the maximum number of edges in the undirected graph of Nodes N? Each node can have an edge over every other N-1 node in an undirected graph. Thus, the total number of edges possible will be N * (N - 1), but here, in the undirected graph, the two edges between two nodes will be the same. So we need to remove one of them. Therefore the total number of edges possible is N * (N - 1)/2.
What is the topological sort? For a Directed Acyclic Graph (DAG), topological sorting is a linear ordering of vertices in which vertex u comes before v in the ordering for every directed edge u v. If the graph is not a DAG, topological sorting is not possible.
Is there any other Data Structures and Algorithms content in Coding Ninjas Studio? Yes, Coding Ninjas Studio allows you to practice coding as well as answer frequently asked interview questions. The more we practice, the more likely we are to acquire a job at our dream company.
Key Takeaways
In this article, we have extensively discussed the problem of the Alien Dictionary. We saw all two methods to solve the problem ‘Alien Dictionary”.We hope that this blog has helped you enhance your knowledge of ‘The Alien Dictionary’ and if you would like to learn more, check out our articles on Library. Do upvote our blog to help other ninjas grow. Happy Coding!
34+ registered 
