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 "".

Note:

  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.
[code lang="java"]
class Solution {
    public String alienOrder(String[] words) {
        
    }
}
[code]

Idea – 1

Since words are lexicographically sorted, if two consecutive words, word1 and word2 (word1 < word2) first differ in the i-th letter, we have an ordering between the two letters like: word1.charAt(i) < word2.charAt(i). We can thus build a directed graph where nodes are the distinct letters in the given list of words and an edge nodeA -> nodeB exists if nodeA’s letter < nodeB’s letter (found from the earlier rule). For the first example the graph would look like:
A topological sort order of the vertices in this graph will give the required ordering of the letters. If a cycle is found, there is no valid ordering. If there are n words with longest having length m, constructing the graph and doing topological sort both would require time O(n\cdot m). The size of the graph would also be O(n\cdot m).
Note – 1
Between two consecutive words after the letter where they mismatch, the ordering between rest of the letters cannot be determined, so we can stop processing there.
Note – 2
Between three consecutive words we only need to compare word1 with word2 and word2 with word3 – we do not need to compare word1 with word3. In scenario1 no new information comes from comparing word1 with word3. And scenario2 is illegal, because word3 would be closer to word1 than word2. 
[code lang="java"]
class Solution {
    public String alienOrder(String[] words) {
        Digraph g = new Digraph(words);
        
        for(int i = 0; i < words.length-1; ++i)
        {
            String current = words[i];
            String next = words[i+1];
            
            int max = Math.min(current.length(), next.length());
            int j = 0;
            while(j < max)
            {
                if(current.charAt(j) != next.charAt(j))
                {
                    break;
                }
                
                ++j;
            }
            
            if(j < max)
            {
                g.addEdge(current.charAt(j), next.charAt(j));
            }
        }
        
        StringBuilder order = new StringBuilder();
        for(char c : g.getTopologicalOrder())
        {
            order.append(c);
        }
        
        return order.toString();
    }
}

class Digraph
{
    HashMap<Character, HashSet<Character>> adjacencyList;
    LinkedList<Character> topologicalOrder;
    
    HashSet<Character> visited;
    HashSet<Character> active;
    
    boolean hasCycle;
    
    public Digraph(String[] words)
    {
        adjacencyList = new HashMap<>();
        
        for(String w : words)
        {
            for(int i = 0; i < w.length(); ++i)
            {
                char c = w.charAt(i);
                adjacencyList.putIfAbsent(c, new HashSet<>());
            }
        }
        
        visited = new HashSet<>();
        active = new HashSet<>();
    }
    
    public void addEdge(char u, char v)
    {
        adjacencyList.get(u).add(v);
    }
    
    public List<Character> getTopologicalOrder()
    {
        if(hasCycle)
        {
            return new LinkedList<>();
        }

        if(topologicalOrder != null)
        {
            return topologicalOrder;
        }
        
        topologicalOrder = new LinkedList<>();
        for(char v : adjacencyList.keySet())
        {
            if(!hasCycle && !visited.contains(v))
            {
                dfs(v);
            }
        }
        
        if(hasCycle)
        {
            return new LinkedList<>();
        }
        
        return topologicalOrder;
    }
    
    private void dfs(char v)
    {
        visited.add(v);
        active.add(v);
        
        for(char w : adjacencyList.get(v))
        {
            if(!visited.contains(w))
            {
                dfs(w);
            }
            else if(active.contains(w))
            {
                hasCycle = true;
                return;
            }
        }
        
        active.remove(v);
        topologicalOrder.addFirst(v);
    }
}
[code]

Runtime: 4 ms, faster than 73.13% of Java online submissions for Alien Dictionary.Memory Usage: 34.9 MB, less than 93.91% of Java online submissions for Alien Dictionary.

Leave a comment