# 0269. Alien Dictionary
###### tags: `Leetcode` `FaceBook` `Hard` `Topological Sort`
Link: https://leetcode.com/problems/alien-dictionary/
## 思路
这种Topological Sort的题目，都是对于每一个parent，都有一个list存它的children，这样方便做bfs，对于每一个children，都有一个计数来存它有几个parent，如果parent=0，就可以把这个node放进queue里面

这里用set array存graph的原因是有可能比字符a小的某个元素可能重复出现
用map的原因是这样可以通过degree的size判断有没有solution，(也可以用array存～) 没有solution的情况就是产生了循环，导致两个degree都永远大于0

还有一种不合法的测资是"abc","ab"但题目中已经说了按照increasing order排的了，理论上来说不应该有这种情况，但是为了通过这道题还是要处理，处理的方法就是在建图的时候，拿到两个字符串，a和b前面全都一样，但是a比b长，直接return

由于有可能出现只有一个单词的情况，或者有字母没有被排序到，但是还是要把所有出现过的字符都输出，因此在一开始就把所有出现过的字母都加进degree里面

**有向图所以要分开存parent的所有child以及child的parent个数
如果可能重复出现，就用list of set存parent的所有child
如果不会，就用list of list
无向图存每个node的所有边即可，这样就通过一个```List<List<Integer>>```知道所有信息～(例如: [0310. Minimum Height Trees](https://hackmd.io/2yyf1znOQlCdQ-3mRGkkSw))**

## Code

class Solution {
    public String alienOrder(String[] words) {
        Set<Character>[] graph = new Set[26];
        Map<Character, Integer> degree = new HashMap<>();
        int count = 0;
        for(int i = 0;i < words.length;i++){
            char[] charArray= words[i].toCharArray();
            for(char c:charArray){
                degree.put(c,0);
            }
        }
        for(int i = 0;i < words.length-1;i++){
            boolean equal = true;
            String word1 = words[i];
            String word2 = words[i+1];
            int s1 = 0;
            int s2 = 0;
            while(s1<word1.length() && s2<word2.length()){
                if(word1.charAt(s1)!=word2.charAt(s2)){
                    if(graph[word1.charAt(s1)-'a']==null) graph[word1.charAt(s1)-'a']=new HashSet<>();
                    if(!graph[word1.charAt(s1)-'a'].contains(word2.charAt(s2))){
                        graph[word1.charAt(s1)-'a'].add(word2.charAt(s2));
                        degree.put(word2.charAt(s2), degree.getOrDefault(word2.charAt(s2),0)+1);
                    }
                    equal = false;
                    break;
                }
                s1++;
                s2++;
            }
            if(equal && word1.length()>word2.length()) return "";
        }
        
        Queue<Character> q = new LinkedList<>();
        for(Character c:degree.keySet()){
            if(degree.get(c)==0) q.add(c);
        }
        
        StringBuilder ans = new StringBuilder();
        while(!q.isEmpty()){
            char curr = q.poll();
            ans.append(curr);
            for(char next:(graph[curr-'a']==null?new HashSet<Character>():graph[curr-'a'])){
                degree.put(next, degree.get(next)-1);
                if(degree.get(next)<=0) q.add(next);
            }
        }
        if(ans.length()!=degree.size()) return "";
        return ans.toString();
    }
}