# Alien Dictionary

Solution to Alien Dictionary problem: Here, we are going to learn about a famous problem known as Alien Dictionary and it's solution.
Submitted by Souvik Saha, on May 08, 2019

Problem Statement:

Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.

Example:

```    List of words: {'aba', 'ddc', 'cab', 'ebd', 'cc' }
Output: order of the characters is :abde c
List of words: {'abb', 'caa', 'dda', 'bba' }
Output: order of the characters is :acdb
```

Algorithm:

To solve this problem we follow this approach:

1. First, we take two strings and compare each element of the same level of two string (like "aba", "ddc").
2. After making the comparison we make an edge between them (a → d, b → d, a → c).
3. After comparing all the strings we draw the graph between the letters.
4. After getting the graph we topologically sort that graph. (to know about the topological sort).

## C++ Implementation for alien dictionary

```#include <bits/stdc++.h>
using namespace std;
void addedge(list<int>* ls, int x, int y)
{
ls[x].push_back(y);
}
string topological_sort(list<int>* ls, int k)
{
char arr[k];
stack<int> s;
set<int> st;
int ind = k - 1;
for (int i = k - 1; i >= 0; i--) {
if (st.find(i) == st.end()) {
s.push(i);
st.insert(i);
//check all the non visited nodes
while (!s.empty()) {
int p = s.top();
list<int>::iterator it;
int temp = 0;
//check its adjacent non visited nodes
for (it = ls[p].begin(); it != ls[p].end(); it++) {
if (st.find(*it) == st.end()) {
st.insert(*it);
s.push(*it);
temp = 1;
}
}
//if all adjaceny nodes are visited
//then pop that element from stack
if (temp == 0) {
char ch = (char)(p + 'a');
arr[ind] = ch;
ind--;
s.pop();
}
}
}
}
return arr;
}
string printOrder(string dict[], int k)
{
list<int> ls[k];
for (int i = 0; i < k - 1; i++) {
string word1 = dict[i];
string word2 = dict[i + 1];
//comparing the two strings
for (int j = 0; j < min(word1.length(), word2.length()); j++) {
if (word1[j] != word2[j]) {
//make an egde between them
addedge(ls, word1[j] - 'a', word2[j] - 'a');
break;
}
}
}

}

int main()
{
string dict = { "abb", "caa", "dda", "ba" };
cout << printOrder(dict, 4);
return 0;
}
```

Output

```acdb
```