Java Trie+Topological sorting for early termination


  • 0

    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
                            outEdges.get(lastChar).add(s[i]);         // add the edge and increase the inEdge count
                            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 add(root.nexts[c], s, i+1);
            }
            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 "";
        }
    }
    

Log in to reply
 

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