The dictionary provides details about the order of alphabetical characters. For example, if abc, abd are two words where abd comes after abc, it means c is smaller than d. But if order is opposite this implies d is smaller than c. In this article, we will learn how to solve the Alien Dictionary problem.
What is the Alien Dictionary Problem?
In the Alien Dictionary problem, we are given an array containing words in the order it was written in a dictionary. This dictionary is not the same as our actual dictionary. You have to find the order of characters in that dictionary.
For example, array = [ “acd”, “dc”, “ca”]. This means the actual order of letters is a, d, c.
Topological Sorting Approach
In topological sorting, we find out the order of the nodes. As in this case, we have to find out the order of the characters so we will assume characters a individual nodes, and the edges represent the relative order between them.
We will first construct the graph by assuming each letter is an individual character and then construct the directed edges which denotes the direction in which we are moving. If we find out that the graph contains a cycle then topological sorting is not possible if not then return the ans.
Let’s understand this approach step by step:
- First, create an adjacency list that stores the total number of unique characters in the array.
- Now create the edges by comparing the characters of the adjacent words. Create the edges between the first characters which does not match.
- Now find if the graph contains a cycle or not. If it contains cycle return the order is not possible to find.
- If not find the topological order of the given graph and return the order.
Let’s examine the code for the above process.
C++ Code
Here is how to implement topological sorting to solve Alien Dictionary problem:
#include<bits/stdc++.h>
using namespace std;
vector<int>cunt(26,0);
void add_edge(vector<vector<int>>&list, char a, char b){
list[a-'a'].push_back(b-'a');
}
void dfs(vector<vector<int>>& list, vector<int>& temp, int curr, bool& flag)
{
temp[curr] = 1;
for (int i = 0; i < list[curr].size(); i++) {
int j = list[curr][i];
if (temp[j] == 1) {
flag = true;
return;
}
else if (temp[j] == 0) {
dfs(list, temp, j, flag);
}
}
temp[curr] = 2;
return ;
}
bool is_cycle(vector<vector<int>>& list, vector<int>temp){
bool flag = false;
for(int i=0; i<26; i++){
if(list[i].size()){
if(temp[i] == 0) dfs(list, temp, i, flag);
}
}
return flag;
}
void topological_sort_fun(vector<vector<int>>&list, int curr, vector<bool>& visited, stack<char>& st)
{
visited[curr] = true;
for (int i = 0; i < list[curr].size(); i++) {
int x = list[curr][i];
if (visited[x] == false) {
topological_sort_fun(list, x, visited, st);
}
}
st.push('a' + curr);
return;
}
stack<char> topological_sort(vector<vector<int>>& list){
vector<bool>visited(26,false);
stack<char>st;
for(int i=0;i<26;i++){
if(visited[i]==false && cunt[i]>0){
topological_sort_fun(list, i, visited, st);
}
}
return st;
}
vector<char> find_order(vector<string>& arr){
// first we find out how many unique characters are there
for(int i=0;i<arr.size();i++){
for(int j=0;j<arr[i].size();j++){
cunt[arr[i][j]-'a']++;
}
}
// finding the edges by looking at adjacent elements
int n = arr.size();
vector<vector<int>>list(26);
for (int i = 0; i < n - 1; i++) {
int j = 0;
int sz_1 = arr[i].size();
int sz_2 = arr[i+1].size();
while (j < sz_1 && j < sz_2) {
if (arr[i][j] != arr[i+1][j]) {
add_edge(list, arr[i][j], arr[i+1][j]);
break;
}
j++;
}
}
vector<int>temp(26, 0);
// if graph consist of cycle or not
if(is_cycle(list, temp)){
cout<<"No valid order is possible";
return {};
}
// find the topologicalSort
stack<char>st = topological_sort(list);
vector<char>res;
while(st.size()){
char ch = st.top();
res.push_back(ch);
st.pop();
}
return res;
}
int main(){
vector<string>arr = {"bcd", "ddc", "dcb", "ab"};
vector<char>v = find_order(arr);
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
cout<<endl;
return 0;
}Java Code
Here is the Java program to do the same:
import java.util.*;
public class Main {
static int[] count = new int[26];
static void addEdge(ArrayList<ArrayList<Integer>> list, char a, char b) {
list.get(a - 'a').add(b - 'a');
}
static void dfs(ArrayList<ArrayList<Integer>> list, int[] temp, int curr, boolean[] flag) {
temp[curr] = 1;
for (int i = 0; i < list.get(curr).size(); i++) {
int j = list.get(curr).get(i);
if (temp[j] == 1) {
flag[0] = true;
return;
} else if (temp[j] == 0) {
dfs(list, temp, j, flag);
}
}
temp[curr] = 2;
}
static boolean isCycle(ArrayList<ArrayList<Integer>> list, int[] temp) {
boolean[] flag = {false};
for (int i = 0; i < 26; i++) {
if (!list.get(i).isEmpty() && temp[i] == 0) {
dfs(list, temp, i, flag);
}
}
return flag[0];
}
static void topologicalSortFun(ArrayList<ArrayList<Integer>> list, int curr, boolean[] visited, Stack<Character> st) {
visited[curr] = true;
for (int i = 0; i < list.get(curr).size(); i++) {
int x = list.get(curr).get(i);
if (!visited[x]) {
topologicalSortFun(list, x, visited, st);
}
}
st.push((char)('a' + curr));
}
static Stack<Character> topologicalSort(ArrayList<ArrayList<Integer>> list) {
boolean[] visited = new boolean[26];
Stack<Character> st = new Stack<>();
for (int i = 0; i < 26; i++) {
if (!visited[i] && count[i] > 0) {
topologicalSortFun(list, i, visited, st);
}
}
return st;
}
static ArrayList<Character> findOrder(ArrayList<String> arr) {
for (String s : arr) {
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
}
int n = arr.size();
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for (int i = 0; i < 26; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < n - 1; i++) {
int j = 0;
int sz_1 = arr.get(i).length();
int sz_2 = arr.get(i + 1).length();
while (j < sz_1 && j < sz_2) {
if (arr.get(i).charAt(j) != arr.get(i + 1).charAt(j)) {
addEdge(list, arr.get(i).charAt(j), arr.get(i + 1).charAt(j));
break;
}
j++;
}
}
int[] temp = new int[26];
if (isCycle(list, temp)) {
System.out.println("No valid order is possible");
return new ArrayList<>();
}
Stack<Character> st = topologicalSort(list);
ArrayList<Character> res = new ArrayList<>();
while (!st.isEmpty()) {
char ch = st.pop();
res.add(ch);
}
return res;
}
public static void main(String[] args) {
ArrayList<String> arr = new ArrayList<>(Arrays.asList("bcd", "ddc", "dcb", "ab"));
ArrayList<Character> v = findOrder(arr);
for (char c : v) {
System.out.print(c + " ");
}
System.out.println();
}
}Python Code
Python can also be used to solve this leetcode problem:
count = [0] * 26
def add_edge(list, a, b):
list[ord(a) - ord('a')].append(ord(b) - ord('a'))
def dfs(list, temp, curr, flag):
temp[curr] = 1
for i in range(len(list[curr])):
j = list[curr][i]
if temp[j] == 1:
flag[0] = True
return
elif temp[j] == 0:
dfs(list, temp, j, flag)
temp[curr] = 2
def is_cycle(list, temp):
flag = [False]
for i in range(26):
if list[i] and temp[i] == 0:
dfs(list, temp, i, flag)
return flag[0]
def topological_sort_fun(list, curr, visited, st):
visited[curr] = True
for i in range(len(list[curr])):
x = list[curr][i]
if not visited[x]:
topological_sort_fun(list, x, visited, st)
st.append(chr(ord('a') + curr))
def topological_sort(list):
visited = [False] * 26
st = []
for i in range(26):
if not visited[i] and count[i] > 0:
topological_sort_fun(list, i, visited, st)
return st
def find_order(arr):
global count
for s in arr:
for c in s:
count[ord(c) - ord('a')] += 1
n = len(arr)
list = [[] for _ in range(26)]
for i in range(n - 1):
j = 0
sz_1 = len(arr[i])
sz_2 = len(arr[i + 1])
while j < sz_1 and j < sz_2:
if arr[i][j] != arr[i + 1][j]:
add_edge(list, arr[i][j], arr[i + 1][j])
break
j += 1
temp = [0] * 26
if is_cycle(list, temp):
print("No valid order is possible")
return []
st = topological_sort(list)
res = []
while st:
ch = st.pop()
res.append(ch)
return res
if __name__ == "__main__":
arr = ["bcd", "ddc", "dcb", "ab"]
v = find_order(arr)
for c in v:
print(c, end=" ")
print()Output:
b d c a Complexity Analysis
The time complexity for implementing topological sorting to solve the Alien Dictionary problem is O(n + k), where n is the total number of words in the array and k is the total unique characters in the array. As we are making an adjacency list having a node equal to k.
The space complexity for the above code is O(n + k). As there are total n different words and we are comparing each adjacent word and based on this we will push that character into one of the nodes.
Conclusion
This article helps us to understand the topological sort in more depth to verify an Alien Dictionary. We find out how we can apply topological sort when we have to find the order of nodes in the graph.
