# Alien Dictionary

This page explains Java solution to problem `Alien Dictionary` using `Topological Sorting` algorithm.

## Problem Statement

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input: ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"

Example 2:

Input: ["z", "x"]
Output: "zx"

Example 3:

Input: ["z", "x", "z"]
Output: ""
Explanation: The order is invalid, so return "".

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class AlienDictionary {
public String alienOrder(String[] words) {
/**
wrt
wrf
er
ett
rftt

Building Ingress & Dependency Map
w -> 0
r -> 1
t -> 1
f -> 1
e -> 1

t -> f
w -> e
r -> t
e -> r

Topological Sorting
wertf
*/

HashMap<Character, Integer> ingress = new HashMap<>();
HashMap<Character, HashSet<Character>> dependencyMap = new HashMap<>();
for(String word: words) {
for(int i = 0; i < word.length(); i++) ingress.put(word.charAt(i), 0);
}

for(int i = 0; i < words.length - 1; i++) {
String word1 = words[i];
String word2 = words[i + 1];
boolean found = false;
for(int index = 0; index < Math.min(word1.length(), word2.length()); index++) {
char ch1 = word1.charAt(index);
char ch2 = word2.charAt(index);
if(ch1 != ch2) {
HashSet<Character> set = dependencyMap.getOrDefault(ch1, new HashSet<>());
if(!set.contains(ch2)) {
ingress.put(ch2, ingress.getOrDefault(ch2, 0) + 1);
dependencyMap.put(ch1, set);
}
found = true;
break;
}
}
if(!found && word1.length() > word2.length()) return "";
}

for(Map.Entry<Character, Integer> entry: ingress.entrySet()) {
if(entry.getValue() == 0) q.offer(entry.getKey());
}

StringBuilder sb = new StringBuilder();
while(!q.isEmpty()) {
char ch = q.poll();
sb.append(ch);
if(dependencyMap.containsKey(ch)) {
for(Character dependantCh: dependencyMap.get(ch)) {
ingress.put(dependantCh, ingress.getOrDefault(dependantCh, 0) - 1);
if(ingress.get(dependantCh) == 0) q.offer(dependantCh);
}
}
}

return ingress.size() == sb.length() ? sb.toString() : "";
}
}
``````

## Time Complexity

O(V + E) Where
V is total number of characters in input array words(Vertices)
E is total number of connections/dependency generated(Edges)

## Space Complexity

O(V + E)
V is total number of characters in input array words(Vertices)
E is total number of connections/dependency generated(Edges)