String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding


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.


    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


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)
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()) {
            //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()) {
                        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;
    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');

    return topological_sort(ls, k);

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



Comments and Discussions!

Load comments ↻

Copyright © 2024 www.includehelp.com. All rights reserved.