# Java Trie+Topological sorting for early termination

• The solution using Trie for remembering the prefix and then find the order. The advantage is that certain loop can be detected while building the Trie.
For example, the case of ["xa","xb","xc","xd","xb"].
We remember the letter of latest added child node.
After adding "xa", the latest letter of Trie 'x' will be 'a'.
When adding "xb" we know that prefix "xb" does not exist so we find a order of `a->b`.
Following the same rule, we can find `a->b`, `b->c`, `c->d`.
After adding "xa","xb","xc","xd", the latest letter of Trie 'x' will be 'd'.
When adding "xb" we know that prefix "xb" exist so it is placed at the wrong order so we can terminate.
Then, the rest is just topological sorting.

``````public class Solution {
class Trie {
Character lastChar = null;
Trie[] nexts = new Trie[26];
}
Map<Character, Set<Character>> outEdges = new HashMap<>();
Map<Character, Integer> inEdges = new HashMap<>();
boolean add(Trie root, char[] s, int i){
if (i < s.length) {
int c = s[i]-'a';
inEdges.putIfAbsent(s[i],0); // initialize if a letter show up at first time
Character lastChar = root.lastChar; // the last new add child of this Trie
if (root.nexts[c]==null) { // add a new child Trie
root.nexts[c]=new Trie();
if (lastChar != null ) { // not the first child Trie
outEdges.putIfAbsent(lastChar, new HashSet<>()); // initialize if this edge does not exist
if (! outEdges.get(lastChar).contains(s[i])){ // not a duplicated edge
inEdges.put(s[i], inEdges.get(s[i])+1);
}
if (outEdges.containsKey(s[i]) && outEdges.get(s[i]).contains(lastChar) ) //loop
return false;
}
root.lastChar = s[i];
} else { // passing a existing Trie
if (s[i] != lastChar) // loop
return false;
}
}
return true;
}

boolean findOrder(StringBuilder ret){
if (inEdges.isEmpty()) return true; // all the letters are in place
int size = ret.length();
for (char c: new ArrayList<>(inEdges.keySet()) ) {
if (inEdges.get(c)==0) {
ret.append(c);
inEdges.remove(c);
for (char next: outEdges.getOrDefault(c, new HashSet<>())){
inEdges.put(next, inEdges.get(next)-1);
}
}
} // if there are letters left and none of them have more than one inEdge then there is loop
return size == ret.length() ? false: findOrder(ret);
}
public String alienOrder(String[] words) {
if (words==null || words.length==0) return "";
Trie root = new Trie();
for (String word: words) {
if (! add(root, word.toCharArray(), 0)) return "";
}
StringBuilder ret = new StringBuilder();
if ( findOrder(ret) ) return ret.toString();
return "";
}
}
``````

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