# Java AC solution, Topological sort

• The idea is to use topological sort.
basically find the first char with idx i that is different in two word w1, w2, generate a rule w1[i] -> w2[i]. Iterate the whole array to generate rules and use standard topological sort algorithm to sort the rules.

``````public class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> map = new HashMap<>();
Map<Character, Integer> inverseMap = new HashMap<>();
Set<Character> set = new HashSet<>();
for (int i=0; i<words.length-1; i++) {
int m=0;
while(m < words[i].length() && m < words[i+1].length()) {
char c1 = words[i].charAt(m);
char c2 = words[i+1].charAt(m);
if (c1 != c2) {
if (!map.containsKey(c1))
map.put(c1, new HashSet<>());
if (!inverseMap.containsKey(c2))
inverseMap.put(c2, 1);
else
inverseMap.put(c2, inverseMap.get(c2)+1);
}
break;
}
m++;
}
if (m == words[i+1].length() && words[i].length() > m) return "";
}

Deque<Character> q = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
for (char c: set) {
if (!inverseMap.containsKey(c))
q.offer(c);
}

while(!q.isEmpty()) {
char c1 = q.poll();
sb.append(c1);
if (map.containsKey(c1)) {
for (char c2: map.get(c1)) {
if (inverseMap.get(c2) == 1)
q.offer(c2);
inverseMap.put(c2, inverseMap.get(c2)-1);
}
}
}
return sb.length() == set.size() ? sb.toString() : "";
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.