269. Alien Dictionary

https://www.lintcode.com/problem/alien-dictionary/description

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

Note:

1. You may assume all letters are in lowercase.

2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.

3. If the order is invalid, return an empty string.

4. There may be multiple valid order of letters, return any one of them is fine.

给定一堆词，它们按某种字符顺序排好了序，让求出满足input的一种字符顺序。比如[ "wrt", "wrf", "er", "ett", "rftt" ]

wrt>wrf =>t>f, wrf>er=>w>e，er>et=>r>t，ett>rftt=>e>r， 因此可得出w>e>r>t>f。也就是说给定了一系列顺序，要求返回根据顺序遍历的结果，即拓扑排序。先根据input的单词生成单个字符之间的顺序对，如t>f, r>t等。再对字符顺序对做拓扑排序。

class Solution {
public:
    /**
     * @param words: a list of words
     * @return: a string which is correct order
     */
    string alienOrder(vector<string> &words) {
        unordered_map<char, unordered_set<char>> edges;
        unordered_map<char, int> inorder;
        for (int i = 1; i < words.size(); ++i) {
            const auto &pre = words[i - 1], &cur = words[i];
            int j = 0, mi = min(pre.length(), cur.length());
            for (; j < mi; ++j) {
                if (pre[j] != cur[j]) {
                    edges[pre[j]].insert(cur[j]);
                    if (!inorder.count(cur[j])) inorder[cur[j]] = 0;
                    if (!inorder.count(pre[j])) inorder[pre[j]] = 0;
                    ++inorder[cur[j]];
                    break;
                }
            }
            if (j == mi && cur.length() < pre.length()) return "";
        }
        set<char> chars;
        for (const auto w : words) {
            for (const auto n : w) {
                chars.insert(n);
            }
        }
        queue<char> q;
        for (const auto &p : inorder) {
            if (p.second == 0) q.push(p.first);
        }
        string res;
        while (!q.empty()) {
            const auto &t = q.front();
            res.push_back(t);
            chars.erase(t);
            for (const auto c : edges[t]) {
                --inorder[c];
                if (inorder[c] == 0) q.push(c); 
            }
            q.pop();
        }
        // If the order is invalid, return an empty string.
        if (res.length() != inorder.size()) return "";
        // There may be multiple valid order of letters, return the smallest in normal lexicographical order
        int i = 0;
        string r;
        while (!chars.empty() && i < res.size()) {
            const auto a = *chars.begin(), b = res[i];
            if (a < b) {
                r += a;
                chars.erase(a);
            } else {
                r += b;
                ++i;
            }
        }
        for (const auto c : chars) r += c;
        for (; i < res.size(); ++i) r += res[i];
        return r;
    }
};