This page explains Java solution to problem Alien Dictionary
using Topological Sorting
algorithm.
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:Example 2:Input: ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Example 3:Input: ["z", "x"]
Output: "zx"
Input: ["z", "x", "z"]
Output: ""
Explanation: The order is invalid, so return "".
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)) {
set.add(ch2);
ingress.put(ch2, ingress.getOrDefault(ch2, 0) + 1);
dependencyMap.put(ch1, set);
}
found = true;
break;
}
}
if(!found && word1.length() > word2.length()) return "";
}
Queue<Character> q = new LinkedList<>();
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() : "";
}
}
O(V + E) Where
V is total number of characters in input array words(Vertices)
E is total number of connections/dependency generated(Edges)
O(V + E)
V is total number of characters in input array words(Vertices)
E is total number of connections/dependency generated(Edges)