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 "".

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

相同的c2，只需要存一次（没有就新存有就不存），反正如果存过就必须退出了（返回一组即可不用重复加）

"["za","zb","ca","cb"]" How is this test case handled. 
It should give out an empty string as the order can not be decided from the words given. but instead it returns "azbc".

回答：we can only now z-> c and a-> b
so 'azbc' is right but right result is not limited to this only one.
you can test 'zcab', 'abzc' are will all right as it is topological sort

结果字符串长度不等于度数（不是不等于单词数）

["z","z"]的度数 = 字符串长度1
正常，应该返回"z"而不是""

［思维问题］：

忘了拓扑排序用BFS怎么写了

［英文数据结构或算法，为什么不用别的数据结构或算法］：

DFS写拓扑排序似乎都很麻烦

存点到点的对应关系，用map（其中的字符必须存成包装类Character,但是循环的时候可以写char）

        //存每个点的入度
        Map<char, Integer> degree = new HashMap<>();
        //存c1到c2...的对应关系
        Map<char, Set<char>> map = new HashMap<>();

［一句话思路］：

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

出现index[i + 1]时，需要提前备注把上线变为n - 1

［二刷］：

BFS的时候别忘了吧把取出的c1添加到结果中去. 而且必须现有c1的key才能扩展。

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

c1 c2都要先判断一下有没有，再存

［复杂度］：Time complexity: O(n^2 单词数*字母数) Space complexity: O(n)

［算法思想：递归/分治/贪心］：

［关键模板化代码］：

BFS的存储和扩展是两个独立的步骤，扩展时必须先判断key是否存在，再做扩展

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

class Solution {
    public String alienOrder(String[] words) {
        //ini:HashMap<Char, Integer> degree, store all chars into hashmap, String res
        //存每个点的入度
        Map<Character, Integer> degree = new HashMap<>();
        //存c1到c2...的对应关系
        Map<Character, Set<Character>> map = new HashMap<>();
        String res = "";
        for (String word : words) {
            for (char c : word.toCharArray()) 
                degree.put(c, 0);
        }
        
        //compare and store, n - 1
        for (int i = 0; i < words.length - 1; i++) {
            String cur = words[i];
            String next = words[i + 1];
            int smallerLen = Math.min(cur.length(), next.length());
            
            for (int j = 0; j < smallerLen; j++) {
                char c1 = cur.charAt(j);
                char c2 = next.charAt(j);
                
                if (c1 != c2) {
                    //new set
                    Set<Character> set = new HashSet<>();
                    //contains c1
                    if (map.containsKey(c1)) set = map.get(c1);
                    
                    //not contain c2
                    if (!set.contains(c2)) {
                        set.add(c2);
                        map.put(c1, set);
                        degree.put(c2, degree.get(c2) + 1);
                    }
                    break;
                }
            }
        }
        
        //bfs, get answer
        Queue<Character> q = new LinkedList<>();
        for (char c : degree.keySet()) {
            if (degree.get(c) == 0) q.offer(c);
        }
        
        
        while (!q.isEmpty()) {
            char c1 = q.remove();
            res += c1;
            if (map.containsKey(c1)) {
                for (char c2 : map.get(c1)) {
                degree.put(c2, degree.get(c2) - 1);
                if (degree.get(c2) == 0) q.offer(c2);
            }
            }
        }
        
        //cc at end
        if (res.length() != degree.size()) return "";
        
        return res;
}
}

View Code