题目

现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。
假设，您并不知道其中字母之间的先后顺序。但是，会收到词典中获得一个 不为空的 单词列表。因为是从词典中获得的，所以该单词列表内的单词已经 按这门新语言的字母顺序进行了排序。
您需要根据这个输入的列表，还原出此语言中已知的字母顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/alien-dictionary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

大致思路就是根据字母出现的顺序先构造出图来，
然后进行一下拓扑排序就可以了

构造图的过程就是遍历字符串，
找到第i个和第i+1个字符串第一对不同的字母，然后建立一对关系。

建立完图排一个拓扑序就ok了。

代码

class Solution {
private:
    int cnt;
    vector<int> in_degree;
    vector<vector<int>> graph;
    
    void init_graph(vector<string>& words) {
        for (char c : words[0]) 
            if (in_degree[c - 'a'] == -1) ++cnt,in_degree[c - 'a'] = 0;
        for (int i = 0; i < words.size() - 1; i++) {
            for (char c : words[i + 1]) 
                if (in_degree[c - 'a'] == -1) ++cnt,in_degree[c - 'a'] = 0;
            for (int j = 0; j < words[i].size(); j++) {
                char from = words[i][j], to = words[i + 1][j];
                if (from == to) continue;
                graph[from - 'a'].push_back(to - 'a');
                ++in_degree[to - 'a'];
                break;
            }
        }
    }
    
    string topology_sort() {
        string ans = "";
        
        queue<int> q;
        for (int i = 0; i < in_degree.size(); i++) {
            if (in_degree[i] > 0 || in_degree[i] == -1) continue;
            q.push(i);
            ans += (i + 'a');
        }
        
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int from = q.front(); q.pop();
                for (int to : graph[from]) {
                    if (in_degree[to] == 1) {
                        q.push(to);
                        ans += (to + 'a');
                    }
                    --in_degree[to];
                }
            }
        }
        
        return ans.size() == cnt ? ans : "";
    }
    
public:
    Solution():cnt (0), in_degree(26, -1), graph(26) {}
    
    string alienOrder(vector<string>& words) {
        
        init_graph(words);
        
        return topology_sort();
    }
};

执行用时 :4 ms , 在所有 C++ 提交中击败了93.18%的用户
内存消耗 :9 MB , 在所有 C++ 提交中击败了100.00%的用户