题目描述

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

算法1

拓扑排序

相邻两个词的第一个不同的字符 x, y 构成二元顺序 x < y。找出所有的二元顺序，用拓扑排序可以得到字典序。

(1) 用 hashtable 存 in degree 和 邻接链表。
(2) 所有出现的char都是图中的vertex，都要加到degree中，即使没有有向边的关系存在。例如[za, zb, ca, cbf], f也要加到in degree里。而只有边需要加到 邻接链表 中。
(3) 所以遍历words时，每个word的每个char都要加到degree中。如果有下一个词，找到一个不同的char构成边。
(4) 每2个词的第一个不同字母构成一条边，后面不同的字母则不再构成边。
(5) 最后BFS时，queue由degree初始化，所以会访问到所有的char。
(6) 时间复杂度: 假设n个词，平均长度k，则有kv个节点；n个词最多构成n-1个边，topo排序时间复杂度是O(V+E) -> O(kn + n-1)

C++ 代码

string alienOrder(vector<string>& words) {
    unordered_map<char, vector<char>> g;
    unordered_map<char, int> d;

    // build graph
    // all the chars in words should be added to d, otherwise will miss char in vocab
    // but not necessary add to g if no edge. 
    for(int i=0; i<words.size(); i++) {
        for(char c: words[i]) {
            if(d.count(c) == 0) d[c] = 0;
        }

        if( i+1 >= words.size()) continue; // no next word

        for(int j=0; j<min(words[i].size(), words[i+1].size()); j++) {
            char x = words[i][j], y = words[i+1][j];
            if(x!=y) {
                g[x].push_back(y);
                d[y]++;
                break; // 注意 只有第一个不同的char代表了顺序
            }
        }
    }

    // topo sort
    string res = "";
    queue<char> q;
    for(auto kv : d) if(kv.second==0) q.push(kv.first);

    while(q.size()) {
        char u = q.front();
        q.pop();
        res += u;

        for(char v : g[u]) {
            d[v]--;
            if(d[v]==0) q.push(v);
        }
    }

    return res.size()==d.size() ? res : "";
}