269. Alien Dictionary

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.

-------------------------
典型的Topological sort

注意以下个例：
1. 有环
2. ["z", "z"]
3. ["wz", "w"]

class Solution {
    
    private boolean circle = false;
    
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> map = getGraph(words);
        Map<Character, Integer> visited = new HashMap<>();
        
        StringBuilder rt = new StringBuilder();
        for (Character c : map.keySet()) {
            dfs(map, c, visited, rt);    
        }
        
        if (circle) return "";
        return rt.reverse().toString();
    }
    
    private void dfs(Map<Character, Set<Character>> map, char cur,  Map<Character, Integer> visited, StringBuilder sb) {

        if (visited.containsKey(cur) && visited.get(cur) == 1) {
            circle = true;
            return;
        }
        if (visited.containsKey(cur) && visited.get(cur) == -1) return;
        
        visited.put(cur, 1);
        for (Character c : map.get(cur)) {
            dfs(map, c, visited, sb);
        }    

        visited.put(cur, -1);
        sb.append(cur);
    }
    
    private Map<Character, Set<Character>> getGraph(String[] words) {
        Map<Character, Set<Character>> map = new HashMap<>();
        
        for (String w : words) {
            for (int i = 0; i < w.length(); i++) {
                map.put(w.charAt(i), new HashSet<>());
            }    
        }
        
        for (int i = 1; i < words.length; i++) {
            for (int j = 0; j < words[i].length() && j < words[i - 1].length(); j++) {
                char c1 = words[i - 1].charAt(j);
                char c2 = words[i].charAt(j);
                
                if (c1 == c2) continue;
                map.get(c1).add(c2);        
                break;
            }   
        }
        
        return map;
    }
}

ToDo
1.把上面的代码精简以下。
2.用BFS再写一遍