Home » Interview coding problems/challenges

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;
            }
        }
    }

    return topological_sort(ls, k);
}

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

Output

acdb