Alien Dictionary is a type of problem in which we have N-words and they are sorted in alien dictionary order. We need to find the order of the characters. The alien language is also used the lowercase letters but the order of the letters is different. Let’s see how we find the order of the character present in the given words. We create a graph of size 26 where 26 represents the number of possible vertices. We create a graph such that we choose two consecutive words. Now, check the words by comparing them character by character. If we encounter character as unmatched then create an edge between them and move to the next character in both of them. Then, finally, find the topological sorting of the graph which gives us the order of the characters.
Table of Contents
Input Format
First-line contain a number N which represents total words present in alien dictionary. Second-line containing N words separated by an gap.
Output Format
Print the order of the characters present in the words. Note that in all words maximum different characters possible are 26.
Constraint
- ‘a'<=word[i]<=’z’
- 2<=N<=100000
- 1<=word.length()<=200
Algorithm For Alien Dictionary
Step:1 Find the total number(N) of different characters present in the alien dictionary.
Step:2 Create a graph G containing N nodes in such way:
i) Choose two continuous words in the alien dictionary.
ii) Check characters one by one if they not matched then create an edge between them.
iii) Repeat i, ii step till we able to select two contiguous words.
Step:3 Find the topological sorting of the created graph G.
Step:4 Print the character in topological order.
Implementation For Alien Dictionary
/*C++ Implementation of Alien Dictionary Problem.*/
#include<bits/stdc++.h>
using namespace std;
void sorting(int v,bool visited[],stack<int> &s,vector<int> graph[])
{
visited[v]=true;
for(int i=0;i<graph[v].size();i++)
{
if(visited[graph[v][i]]==false)
{
sorting(graph[v][i],visited,s,graph);
}
}
s.push(v);
}
void topological_sort(vector<int> graph[])
{
stack<int> s;
bool visited[27];
memset(visited,false,sizeof(visited));
for(int i=0;i<26;i++)
{
if(visited[i]==false)
{
sorting(i,visited,s,graph);
}
}
/*print the char in topological sorting order.*/
while(!s.empty())
{
char ch = (char) 'a'+s.top();
s.pop();
cout<<ch<<" ";
}
cout<<endl;
}
int main()
{
/*input values.*/
int n;
cin>>n;
string dict[n];
/*take n words as input.*/
for(int i=0;i<n;i++)
{
cin>>dict[i];
}
vector<int> graph[27];
/*create a graph by following algorithm.*/
for(int i=0;i<n-1;i++)
{
string w1=dict[i];
string w2=dict[i+1];
for(int j=0;j<min(w1.size(),w2.size());j++)
{
if(w1[j]!=w2[j])
{
/*add edge w1[j] -> w2[j].*/
graph[w1[j]-'a'].push_back(w2[j]-'a');
/*move to the next contiguous words.*/
break;
}
}
}
cout<<"Order of the character is: ";
topological_sort(graph);
return 0;
}6 hello leetcode teritoroite redimedires avengers warmisetripes
Order of the character is: z y x v u s q p o n m k j i h l t r g f e d c b a w
Time Complexity
O(N+C) where N is the number of words present in the Alien dictionary and C is 26 for all the lower case characters. We use the DFS traversal
to find the topological sorting order of the characters. We know already the time complexity of topological sorting is O(N+E) where N is the nodes and E is the edges present in a graph.
Space Complexity
O(N+C) where N is the number of words present in the Alien dictionary and C is 26 for all the lower case characters. We create a graph or adjacency list in which the size of the adjacency list is 26(C).