1、思路

• 用一个哈希表graph来表示图，它的值是比键字典序更大的字母集合，哈希表inDegrees表示每个字母的入度；

• 比较单词列表中两两相邻的单词，从头找出第一组不同的两个字母，在图中添加一条从较小字母 ch1 指向较大字母 ch2 的边；

• 从入度为 0 的字母开始，进行广度优先搜索的拓扑排序；

• 时间复杂度为 $O(mn)$ ，其中 $m$ 表示单词列表的长度， $n$ 表示平均每个单词的长度。

2、代码

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> graph;
        unordered_map<char, int> inDegrees;

        for (string &word : words)                  //入度初始化
        {
            for (char &ch : word)
            {
                if (inDegrees.find(ch) == inDegrees.end())
                {
                    inDegrees[ch] = 0;
                }
            }
        }

        for (int i = 1; i < words.size(); ++ i)     //计算每个字母的入度
        {
            string w1 = words[i - 1];
            string w2 = words[i];

            int j = 0;
            for (; j < w1.length() && j < w2.length(); ++ j)
            {
                char ch1 = w1[j];
                char ch2 = w2[j];

                if (ch1 != ch2)                 //表示 ch1 较小
                {
                    if (graph[ch1].find(ch2) == graph[ch1].end())
                    {
                        graph[ch1].insert(ch2); //在图中添加一条从 ch1 到 ch2 的边
                        inDegrees[ch2] ++ ;
                    }

                    break;
                }
            }

            //用来判断特殊情况，如 ["abc","ab"]，后一单词是前一单词的前缀，且前一单词更长，为非法字典序
            if (j == w2.length() && w1.length() > w2.length()) return "";
        }

        queue<char> q;
        for (pair<char, int> inDegree : inDegrees)  //将入度为 0 的字母加入队列
        {
            if (inDegree.second == 0)
            {
                q.push(inDegree.first);
            }
        }

        string res = "";
        while (!q.empty())                          //拓扑排序
        {
            char ch = q.front();
            q.pop();
            res += ch;

            for (char next : graph[ch])             //较大单词的入度全部减 1
            {
                inDegrees[next] -- ;
                if (inDegrees[next] == 0)
                {
                    q.push(next);
                }
            }
        }

        // graph.size() 表示所有字母的个数
        return res.length() == graph.size() ? res : "";
    }
};