Open In App

Alien Dictionary

Last Updated : 23 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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

Examples:  

Input: words[] = {“baa”, “abcd”, “abca”, “cab”, “cad”}
Output: Order of characters is ‘b’, ‘d’, ‘a’, ‘c’
Explanation: Note that words are sorted and in the given language “baa” comes before “abcd”, therefore ‘b’ is before ‘a’ in output. Similarly we can find other orders.

Input: words[] = {“caa”, “aaa”, “aab”}
Output: Order of characters is ‘c’, ‘a’, ‘b’

Recommended Practice
Alien Dictionary
Try It!

Alien Dictionary using Topological Sorting:

The idea is to create a directed graph where each character represents a node,and edges between nodes indicate the relative order of characters. If the graph created contains a cycle then a valid order of charcters is not possible else the topological sorting algorithm is applied to the graph to determine the character order.

Following are the detailed steps.

  • Create a directed graph g with number of vertices equal to the number of unique characters in alien language, where each character represents a node and edges between nodes indicate the relative order of characters.
  • Do following for every pair of adjacent words in given sorted array.
    • Let the current pair of words be word1 and word2. One by one compare characters of both words and find the first mismatching characters. 
    • Create an edge in g from mismatching character of word1 to that of word2.
  • If the graph created is DAG (Directed Acyclic Grapgh) then print topological sorting of the above created graph else if the graph contains a cycle then input data is inconsistent and valid order of characters does not exist.

Below is the implementation of above approach:

C++ 
#include <bits/stdc++.h>
using namespace std;

// Function to add a directed edge between characters u and
// v
void addEdge(vector<int> adj[], char u, char v)
{
    adj[u - 'a'].push_back(v - 'a');
}

// Depth-First Search (DFS) function to check for cycles in
// the graph
void dfs(vector<int> adj[], vector<int>& col, int curr,
         bool& isCyclic)
{
    // Mark the current node as visited and in the current
    // path
    col[curr] = 1;
  
    for (int i = 0; i < adj[curr].size(); i++) {
        int x = adj[curr][i];
        if (col[x] == 1) {

            // If the node is already in the current path, a
            // cycle is detected
            isCyclic = true;
          
            return;
        }
        else if (col[x] == 0) {

            // Recursively visit adjacent nodes
            dfs(adj, col, x, isCyclic);
        }
    }

    // Mark the current node as visited and not in the
    // current path
    col[curr] = 2;
}

// Function to check if a cycle exists in the graph using
// DFS
bool checkCycle(vector<int> adj[], vector<int> col, int k)
{
    bool isCyclic = false;
    for (int i = 0; i < k; i++) {
        if (col[i] == 0) {
            dfs(adj, col, i, isCyclic);
        }
    }
    return isCyclic;
}

// DFS-based topological sorting utility function
void topologicalSortUtil(vector<int> adj[], int u,
                         bool visited[], stack<int>& st)
{
    visited[u] = true;
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (!visited[v]) {
            topologicalSortUtil(adj, v, visited, st);
        }
    }
    st.push(u);
}

// Function to perform topological sorting
void topologicalSort(vector<int> adj[], int V)
{
    bool visited[V];
    stack<int> st;

    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            topologicalSortUtil(adj, i, visited, st);
        }
    }

    // Print the characters in topological order
    while (!st.empty()) {
        cout << char(st.top() + 'a') << " ";
        st.pop();
    }
}

// Function to process the words and find the character
// order
void printOrder(string words[], int n)
{
    // To track the frequency of characters
    vector<int> frq(26, 0);

    // Count of unique characters
    int k = 0;

    // Count unique characters and their frequencies
    for (int i = 0; i < n; i++) {
        string s = words[i];
        for (int j = 0; j < s.size(); j++) {
            frq[s[j] - 97]++;
            if (frq[s[j] - 97] == 1)
                k++;
        }
    }

    // Create adjacency list for the graph
    vector<int> adj[k];

    // Build the graph by iterating through adjacent words
    for (int i = 0; i < n - 1; i++) {
        string word1 = words[i];
        string word2 = words[i + 1];

        int j = 0;
        while (j < word1.length() && j < word2.length()) {
            if (word1[j] != word2[j]) {

                // Add edges based on character order
                addEdge(adj, word1[j], word2[j]);

                break;
            }
            j++;
        }
    }

    // Color array for cycle detection
    vector<int> col(k, 0);
    if (checkCycle(adj, col, k)) {
        // Detect and handle cycles
        cout << "Valid Order is not possible\n";
        return;
    }

    // Perform topological sorting and print character order
    topologicalSort(adj, k);
}

// Driver Code
int main()
{
    string words[]
        = { "baa", "abcd", "abca", "cab", "cad" };
    int n = sizeof(words) / sizeof(words[0]);

    printOrder(words, n);

    return 0;
}
Java 
import java.util.*;

public class CharacterOrder {

    // Function to add a directed edge between characters u and v
    static void addEdge(ArrayList<Integer>[] adj, char u, char v) {
        adj[u - 'a'].add(v - 'a');
    }

    // Depth-First Search (DFS) function to check for cycles in the graph
    static void dfs(ArrayList<Integer>[] adj, int[] col, int curr, boolean[] isCyclic) {
        col[curr] = 1;

        for (int i = 0; i < adj[curr].size(); i++) {
            int x = adj[curr].get(i);
            if (col[x] == 1) {
                isCyclic[0] = true;
                return;
            } else if (col[x] == 0) {
                dfs(adj, col, x, isCyclic);
            }
        }

        col[curr] = 2;
    }

    // Function to check if a cycle exists in the graph using DFS
    static boolean checkCycle(ArrayList<Integer>[] adj, int[] col, int k) {
        boolean[] isCyclic = { false };
        for (int i = 0; i < k; i++) {
            if (col[i] == 0) {
                dfs(adj, col, i, isCyclic);
            }
        }
        return isCyclic[0];
    }

    // DFS-based topological sorting utility function
    static void topologicalSortUtil(ArrayList<Integer>[] adj, int u, boolean[] visited, Stack<Integer> st) {
        visited[u] = true;
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u].get(i);
            if (!visited[v]) {
                topologicalSortUtil(adj, v, visited, st);
            }
        }
        st.push(u);
    }

    // Function to perform topological sorting
    static void topologicalSort(ArrayList<Integer>[] adj, int V) {
        boolean[] visited = new boolean[V];
        Stack<Integer> st = new Stack<>();

        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(adj, i, visited, st);
            }
        }

        // Print the characters in topological order
        while (!st.isEmpty()) {
            System.out.print((char) (st.pop() + 'a') + " ");
        }
    }

    // Function to process the words and find the character order
    static void printOrder(String[] words, int n) {
        // To track the frequency of characters
        int[] frq = new int[26];

        // Count of unique characters
        int k = 0;

        // Count unique characters and their frequencies
        for (int i = 0; i < n; i++) {
            String s = words[i];
            for (int j = 0; j < s.length(); j++) {
                frq[s.charAt(j) - 'a']++;
                if (frq[s.charAt(j) - 'a'] == 1)
                    k++;
            }
        }

        // Create adjacency list for the graph
        ArrayList<Integer>[] adj = new ArrayList[k];
        for (int i = 0; i < k; i++) {
            adj[i] = new ArrayList<>();
        }

        // Build the graph by iterating through adjacent words
        for (int i = 0; i < n - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];

            int j = 0;
            while (j < word1.length() && j < word2.length()) {
                if (word1.charAt(j) != word2.charAt(j)) {
                    // Add edges based on character order
                    addEdge(adj, word1.charAt(j), word2.charAt(j));
                    break;
                }
                j++;
            }
        }

        // Color array for cycle detection
        int[] col = new int[k];
        if (checkCycle(adj, col, k)) {
            // Detect and handle cycles
            System.out.println("Valid Order is not possible");
            return;
        }

        // Perform topological sorting and print character order
        topologicalSort(adj, k);
    }

    // Driver Code
    public static void main(String[] args) {
        String[] words = { "baa", "abcd", "abca", "cab", "cad" };
        int n = words.length;

        printOrder(words, n);
    }
}
Python 
# Function to add a directed edge between characters u and v
def addEdge(adj, u, v):
    adj[ord(u) - ord('a')].append(ord(v) - ord('a'))

# Depth-First Search (DFS) function to check for cycles in the graph
def dfs(adj, col, curr, isCyclic):
    # Mark the current node as visited and in the current path
    col[curr] = 1

    for x in adj[curr]:
        if col[x] == 1:
            # If the node is already in the current path, a cycle is detected
            isCyclic[0] = True
            return
        elif col[x] == 0:
            # Recursively visit adjacent nodes
            dfs(adj, col, x, isCyclic)

    # Mark the current node as visited and not in the current path
    col[curr] = 2

# Function to check if a cycle exists in the graph using DFS
def checkCycle(adj, col, k):
    isCyclic = [False]
    for i in range(k):
        if col[i] == 0:
            dfs(adj, col, i, isCyclic)
    return isCyclic[0]

# DFS-based topological sorting utility function
def topologicalSortUtil(adj, u, visited, st):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            topologicalSortUtil(adj, v, visited, st)
    st.append(u)

# Function to perform topological sorting
def topologicalSort(adj, V):
    visited = [False] * V
    st = []

    for i in range(V):
        if not visited[i]:
            topologicalSortUtil(adj, i, visited, st)

    # Print the characters in topological order
    while st:
        print(chr(st.pop() + ord('a')), end=" ")

# Function to process the words and find the character order
def printOrder(words):
    # To track the frequency of characters
    frq = [0] * 26

    # Count of unique characters
    k = 0

    # Count unique characters and their frequencies
    for word in words:
        for char in word:
            frq[ord(char) - ord('a')] += 1
            if frq[ord(char) - ord('a')] == 1:
                k += 1

    # Create adjacency list for the graph
    adj = [[] for _ in range(k)]

    # Build the graph by iterating through adjacent words
    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        j = 0
        while j < len(word1) and j < len(word2):
            if word1[j] != word2[j]:
                # Add edges based on character order
                addEdge(adj, word1[j], word2[j])
                break
            j += 1

    # Color array for cycle detection
    col = [0] * k
    isCyclic = [False]
    if checkCycle(adj, col, k):
        # Detect and handle cycles
        print("Valid Order is not possible")
        return

    # Perform topological sorting and print character order
    topologicalSort(adj, k)

# Driver Code
if __name__ == "__main__":
    words = ["baa", "abcd", "abca", "cab", "cad"]
    printOrder(words)
# This code is contributed by Dwaipayan Bandyopadhyay
C# 
 using System;
using System.Collections.Generic;
using System.Linq;

class Graph
{
    private List<int>[] adj;

    public Graph(int V)
    {
        // Initialize the adjacency list for the graph
        adj = new List<int>[V];
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int u, int v)
    {
        // Add an edge between vertex 'u' and vertex 'v' in the graph
        adj[u].Add(v);
    }

    public bool DFS(int curr, int[] col, ref bool isCyclic)
    {
        // Depth-First Search function to detect cycles in the graph
        col[curr] = 1; // Mark the current vertex as being visited (1)

        foreach (int neighbor in adj[curr])
        {
            if (col[neighbor] == 1)
            {
                // If the neighbor is already being visited, a cycle is detected
                isCyclic = true;
                return true;
            }
            else if (col[neighbor] == 0 && DFS(neighbor, col, ref isCyclic))
            {
                // Recursively visit unvisited neighbors
                return true;
            }
        }

        col[curr] = 2; // Mark the current vertex as visited (2)
        return false;
    }

    public bool CheckCycle(int V)
    {
        // Function to check if the graph contains a cycle
        bool isCyclic = false;
        int[] col = new int[V]; // Initialize color array for vertices

        for (int i = 0; i < V; i++)
        {
            if (col[i] == 0 && DFS(i, col, ref isCyclic))
            {
                return true;
            }
        }

        return isCyclic;
    }

    public void TopologicalSortUtil(int u, bool[] visited, Stack<int> st)
    {
        // Utility function for topological sorting
        visited[u] = true;

        foreach (int v in adj[u])
        {
            if (!visited[v])
            {
                TopologicalSortUtil(v, visited, st);
            }
        }

        st.Push(u);
    }

    public void TopologicalSort(int V)
    {
        // Function to perform topological sorting of the graph
        bool[] visited = new bool[V];
        Stack<int> st = new Stack<int>();

        for (int i = 0; i < V; i++)
        {
            if (!visited[i])
            {
                TopologicalSortUtil(i, visited, st);
            }
        }

        Console.Write("Character Order: ");
        while (st.Count > 0)
        {
            // Print the topological sorting order
            Console.Write((char)(st.Pop() + 'a') + " ");
        }
    }
}

class Program
{
    public static void PrintOrder(string[] words)
    {
        int k = 0;
        int n = words.Length;
        int[] frq = new int[26];
        Array.Fill(frq, 0);

        for (int i = 0; i < n; i++)
        {
            string s = words[i];
            foreach (char c in s)
            {
                frq[c - 'a']++;
                if (frq[c - 'a'] == 1)
                    k++;
            }
        }

        Graph graph = new Graph(k);

        for (int i = 0; i < n - 1; i++)
        {
            string word1 = words[i];
            string word2 = words[i + 1];

            int j = 0;
            while (j < word1.Length && j < word2.Length)
            {
                if (word1[j] != word2[j])
                {
                    graph.AddEdge(word1[j] - 'a', word2[j] - 'a');
                    break;
                }
                j++;
            }
        }

        if (graph.CheckCycle(k))
        {
            Console.WriteLine("Valid Order is not possible");
            return;
        }

        graph.TopologicalSort(k);
    }

    public static void Main(string[] args)
    {
        string[] words = { "baa", "abcd", "abca", "cab", "cad" };
        PrintOrder(words);
    }
}
Javascript 
function addEdge(adj, u, v) {
  adj[u.charCodeAt(0) - 'a'.charCodeAt(0)].push(v.charCodeAt(0) - 'a'.charCodeAt(0));
}

function dfs(adj, col, curr, isCyclic) {
  col[curr] = 1;

  for (let i = 0; i < adj[curr].length; i++) {
    const x = adj[curr][i];
    if (col[x] === 1) {
      isCyclic[0] = true;
      return;
    } else if (col[x] === 0) {
      dfs(adj, col, x, isCyclic);
    }
  }

  col[curr] = 2;
}

function checkCycle(adj, col, k) {
  const isCyclic = [false];
  for (let i = 0; i < k; i++) {
    if (col[i] === 0) {
      dfs(adj, col, i, isCyclic);
    }
  }
  return isCyclic[0];
}

function topologicalSortUtil(adj, u, visited, st) {
  visited[u] = true;
  for (let i = 0; i < adj[u].length; i++) {
    const v = adj[u][i];
    if (!visited[v]) {
      topologicalSortUtil(adj, v, visited, st);
    }
  }
  st.push(u);
}

function topologicalSort(adj, V) {
  const visited = new Array(V).fill(false);
  const st = [];

  for (let i = 0; i < V; i++) {
    if (!visited[i]) {
      topologicalSortUtil(adj, i, visited, st);
    }
  }

  while (st.length > 0) {
    console.log(String.fromCharCode(st.pop() + 'a'.charCodeAt(0)) + " ");
  }
}

function printOrder(words) {
  const frq = new Array(26).fill(0);
  let k = 0;

  for (let i = 0; i < words.length; i++) {
    const s = words[i];
    for (let j = 0; j < s.length; j++) {
      frq[s.charCodeAt(j) - 'a'.charCodeAt(0)]++;
      if (frq[s.charCodeAt(j) - 'a'.charCodeAt(0)] === 1) {
        k++;
      }
    }
  }

  const adj = new Array(k).fill(null).map(() => []);
  
  for (let i = 0; i < words.length - 1; i++) {
    const word1 = words[i];
    const word2 = words[i + 1];

    let j = 0;
    while (j < word1.length && j < word2.length) {
      if (word1[j] !== word2[j]) {
        addEdge(adj, word1[j], word2[j]);
        break;
      }
      j++;
    }
  }

  const col = new Array(k).fill(0);
  if (checkCycle(adj, col, k)) {
    console.log("Valid Order is not possible");
    return;
  }

  topologicalSort(adj, k);
}

const words = ["baa", "abcd", "abca", "cab", "cad"];
printOrder(words);

Output
b d a c

Time Complexity: O(N+K) , where N is number of given words and Kis number of unique characters in given alphabet.
Auxiliary Space: O(N+K) ,



https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Improve
Previous Article
Find if an array of strings can be chained to form a circle | Set 2
Next Article
Remove minimum number of characters so that two strings become anagram

Similar Reads

Check if the given string of words can be formed from words present in the dictionary
Given a string array of M words and a dictionary of N words. The task is to check if the given string of words can be formed from words present in the dictionary. Examples: dict[] = { find, a, geeks, all, for, on, geeks, answers, inter } Input: str[] = { "find", "all", "answers", "on", "geeks", "for", "geeks" }; Output: YES all words of str[] are p
17 min read
Print anagrams together in Python using List and Dictionary
Given an array of words, print all anagrams together. Examples: Input: arr = ['cat', 'dog', 'tac', 'god', 'act'] Output: 'cat tac act dog god' This problem has existing solution please refer Anagrams and Given a sequence of words, print all anagrams together links. We will solve this problem in python using List and Dictionary data structures. Appr
2 min read
Python dictionary, set and counter to check if frequencies can become same
Given a string which contains lower alphabetic characters, we need to remove at most one character from this string in such a way that frequency of each distinct character becomes same in the string. Examples: Input : str = “xyyz” Output : Yes We can remove character ’y’ from above string to make the frequency of each character same. Input : str =
2 min read
Find the first repeated word in a string in Python using Dictionary
Prerequisite : Dictionary data structure Given a string, Find the 1st repeated word in a string. Examples: Input : "Ravi had been saying that he had been there" Output : had Input : "Ravi had been saying that" Output : No Repetition Input : "he had had he" Output : he We have existing solution for this problem please refer Find the first repeated w
4 min read
Dictionary and counter in Python to find winner of election
Given an array of names of candidates in an election. A candidate name in the array represents a vote cast to the candidate. Print the name of candidates received Max vote. If there is tie, print a lexicographically smaller name. Examples: Input : votes[] = {"john", "johnny", "jackie", "johnny", "john", "jackie", "jamie", "jamie", "john", "johnny",
3 min read
Python counter and dictionary intersection example (Make a string using deletion and rearrangement)
Given two strings, find if we can make first string from second by deleting some characters from second and rearranging remaining characters. Examples: Input : s1 = ABHISHEKsinGH : s2 = gfhfBHkooIHnfndSHEKsiAnG Output : Possible Input : s1 = Hello : s2 = dnaKfhelddf Output : Not Possible Input : s1 = GeeksforGeeks : s2 = rteksfoGrdsskGeggehes Outpu
2 min read
Python Dictionary to find mirror characters in a string
Given a string and a number N, we need to mirror the characters from the N-th position up to the length of the string in alphabetical order. In mirror operation, we change ‘a’ to ‘z’, ‘b’ to ‘y’, and so on. Examples: Input : N = 3 paradox Output : paizwlc We mirror characters from position 3 to end. Input : N = 6 pneumonia Output : pneumlmrz We hav
2 min read
Implement a Dictionary using Trie
Implement a dictionary using Trie such that if the input is a string representing a word, the program prints its meaning from the prebuilt dictionary. Examples: Input: str = "map" Output: a diagrammatic representation of an area Input: str = "language" Output: the method of human communication Approach: We can use a Trie to efficiently store string
9 min read
Print all possible combinations of words from Dictionary using Trie
Given an array of strings arr[], for every string in the array, print all possible combinations of strings that can be concatenated to make that word. Examples: Input: arr[] = ["sam", "sung", "samsung"] Output: sam: sam sung: sung samsung: sam sung samsung String 'samsung' can be formed using two different strings from the array i.e. 'sam' and 'sun
12 min read
Python | Implementing Dynamic programming using Dictionary
Dynamic Programming is one way which can be used as an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later. This simple opti
3 min read
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox