269. Alien Dictionary

Leetcode: 269. Alien Dictionary
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.

Hint:

1. need to check the lexicographical order, like ["wrtkj", "wrt"], and ["wrt", "wrtkj"]

Solution:

Main class

class Solution {
    public String alienOrder(String[] words) {
        if(words == null)
            return "";
        //for storing list of connected characters to each character
        Map<Character, Set<Character>> graph = new HashMap<Character, Set<Character>>();
        //for storing indegree count to each character
        Map<Character, Integer> indegree = new HashMap<Character, Integer>();
        //result
        StringBuilder result = new StringBuilder();
        //initialization
        initialize(words, graph, indegree);
        //build graph and set count for each indegree
        buildGraphAndGetIndegree(result, words, graph, indegree);
        //using breadth-first Search to do topological sorting
        topologicalSort(result, graph, indegree);
        //return result
        return result.toString();
    }
  
    private void initialize(String[] words, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
        for(String word:words){
            for(int i = 0; i < word.length(); i++){
                char curr = word.charAt(i);
                //initialize graph for each character with new Set
                if(graph.get(curr) == null){
                    graph.put(curr, new HashSet<Character>());
                }
                //initialize indegree for each character with count 0
                if(indegree.get(curr) == null){
                    indegree.put(curr, 0);
                }
            }
        }
    }

    private void buildGraphAndGetIndegree(StringBuilder result, String[] words, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
        for(int i = 0; i < words.length-1; i++){
            //need compare two adjacent words
            String curr = words[i];
            String next = words[i+1];
            int len = Math.min(curr.length(), next.length());
            //
            boolean breakPoint = false;
            
            for(int j = 0; j < len; j++){
                //need compare two characters which are same position in curr and next
                char from = curr.charAt(j);
                char to = next.charAt(j);
                if(from != to){
                    if(!graph.get(from).contains(to)){
                        graph.get(from).add(to);
                        indegree.put(to, indegree.get(to)+1);
                    }                 
                    breakPoint = true;
                    break;
                }
            }
            if(!breakPoint && curr.charAt(len-1) == next.charAt(len - 1) && len < curr.length()){
                result.setLength(0);
            }
        }
    }

    private void topologicalSort(StringBuilder result, Map<Character, Set<Character>> graph, Map<Character, Integer> indegree){
        Queue<Character> queue = new LinkedList<Character>();
        //traverse indegree, extract characters which count is 0, which is roots
        for(Character key : indegree.keySet()){
            if(indegree.get(key) == 0)
                queue.add(key);
        }
        //BFS search
        while(!queue.isEmpty()){
            //poll out the top element from queue
            char currRoot = queue.poll();
            result.append(currRoot);
            //find the connected characters, pick the indegree of character is 1, and add those to queue
            Set<Character> connectedCharacters = graph.get(currRoot);
            if(connectedCharacters != null){
                for(char character : connectedCharacters){
                    Integer count = indegree.get(character);
                    if(count == 1)
                        queue.add(character);
                    indegree.put(character, count-1); // each time when you traversed at the character, the indegree will reduce 1 for removing the connection from parent point
                }
            }
        }
        //check cycle existing
        if(result.length() != indegree.size())
            result.setLength(0);
    }    
}