269 alien dictionary

more like DICKtionary https://leetcode.com/problems/alien-dictionary/

注意这里不是说每个单词内部的字母顺序是sort的，是单词之间是sort的

思路是错位比较记录edge然后拓扑排序，每一对只有diverge的时候那两个字母能分出大小

但是这道题的edge cases令人发指

首先如果只有一个word要去重sort之后返回

如果前面一个string更长而后面一个string却是它的前缀要返回""

如果有判断不出来顺序的还是要加进indegree map里，我这里没有刻意管顺序，感觉set遍历出来还是有顺序的，感觉不放心的话可以用int array代替？-> 证实了，把treeset换成set是一样的，可能跟hash的方式有关

记得edge查重，如果之前某个edge有add过 indegrees不要加重复了

class Solution {
    public String alienOrder(String[] words) {
        if (words.length == 0) return "";
        if (words.length == 1) {
            char[] array = words[0].toCharArray();
            TreeSet<Character> set = new TreeSet<>();
            for (char ch : array) set.add(ch);
            StringBuilder sb = new StringBuilder();
            for (char ch : set) {
                sb.append(ch);
            }
            return sb.toString();
        }
        Map<Character, Set<Character>> map = new HashMap<>();
        Map<Character, Integer> indegrees = new HashMap<>();
        for (int i = 0; i < words.length - 1; i++) {
            //有test case查这个 我也没办法，除此之外如果不知道顺序可以随便放
            if (words[i].startsWith(words[i + 1]) && words[i].length() > words[i + 1].length()) return "";
            char[] first = words[i].toCharArray();
            char[] second = words[i + 1].toCharArray();
            int j = 0;
            // 不知道顺序的也要放进来
            for (char ch : first) indegrees.put(ch, indegrees.getOrDefault(ch, 0));
            for (char ch : second) indegrees.put(ch, indegrees.getOrDefault(ch, 0));
            
            while (j < first.length && j < second.length && first[j] == second[j]) {
                j++;
            }
            // 每组其实也就只能判断一对字母的顺序
            if (j < first.length && j < second.length && first[j] != second[j]) {
                Set<Character> next = map.get(first[j]);
                if (next == null) next = new HashSet<>();
                //注意这里是固定搭配防止duplicated edges
                if (next.add(second[j])) {
                    map.put(first[j], next);
                    indegrees.put(second[j], indegrees.get(second[j]) + 1);
                }
            }
        }
        
        Queue<Character> queue = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : indegrees.entrySet()){
            if (entry.getValue() == 0) queue.offer(entry.getKey());
        }
        while (!queue.isEmpty()) {
            char ch = queue.poll();
            sb.append(ch);
            Set<Character> next = map.get(ch);
            if (next == null) continue;
            for (char n : next) {
                indegrees.put(n, indegrees.get(n) - 1);
                if (indegrees.get(n) == 0) queue.offer(n);
            }
        }
        
        if (sb.length() < indegrees.size()) return "";
        return sb.toString();
    }
}