Leetcode Graph 269 @Java－CONY的世界

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:
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is: "zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return "".

Note:

You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

如何長出tree，基本上就是word跟word 間第一個不一樣的character，就是一個 edge

ex. wrt, wrf ，第一個不一樣是在 t,f，而表示的就是t -> f （t要在f之前出現）

了解tree怎麼長後，接下來就是有哪些node，這邊因為要排序所有出現過的character，所以一開始先用個set來記錄

基本上只要沒有edge relation 的character 就可以出現，用個int[ ] 來記錄被reference的次數

這邊在check reference count 時就利用之前的set 確定範圍（不用run過整個array)

接下來就是很標準的 topological sort 了，藉由visit 的edge 去減少相對應的refernce count

只要reference count = 0，就表示已經沒有被參考了可以輸出

當所有可以輸出得都輸出後，再確認一下result string是不是與set 大小相等

不相等的情形會發生在有reference count 沒被歸零（如cycle，因為會互卡所以reference count 永遠不會變成0）

class Solution {
    public String alienOrder(String[] words) {
        HashSet<Character> charset = new HashSet();
        HashMap<Character,HashSet<Character>> map = new HashMap();
        int[] count = new int[26];
        Deque<Character> que = new ArrayDeque();
        StringBuilder result = new StringBuilder();
        
        
        for(String word:words){
            for(char c:word.toCharArray())
                charset.add(c);
        }  
        
        for(char c:charset)
            count[c-'a']=0;
        
        BuildGraph(count, words, map);
        
        for(char c:charset){
            System.out.print(c+" "+count[c-'a']);
            if(count[c-'a']==0)
                que.addLast(c);
        }
        while(que.size()>0){
            char c = que.removeFirst();
            System.out.println(c+" ");
            result.append(c);
            if(map.containsKey(c)){
                System.out.print("neigh=");
                for(char neigh:map.get(c)){
                    System.out.print(neigh+" ");
                    count[neigh-'a']--;    
                    if(count[neigh-'a'] == 0)
                        que.add(neigh);
                }
            }
            System.out.println("");
        }
        return (charset.size()==result.length())?result.toString():"";    
    }
    
    void BuildGraph(int[] count, String[] words, HashMap<Character,HashSet<Character>> map){
        char[] previous = words[0].toCharArray();
        for(int index=1; index<words.length; index++){
            char[] cur = words[index].toCharArray();
            int len=Math.min(cur.length, previous.length);
            for(int i=0;i<len;i++){
                if(cur[i] != previous[i]){
                    HashSet<Character> set = (map.containsKey(previous[i]))?map.get(previous[i]):new HashSet();
                    if(!set.contains(cur[i])) {
                        set.add(cur[i]);
                        count[cur[i]-'a']++;
                        map.put(previous[i],set);
                    }
                    break;
                }    
            }
            previous = cur;
        }
    }
}