269

class Solution {
public:
    string alienOrder(vector<string>& words) {
        if(words.size() == 0) return "";
        unordered_map<char, int> indegree;
        unordered_map<char, unordered_set<char>> graph;

        // initialize
        for(int i = 0; i < words.size(); i++) {
            for(int j = 0; j < words[i].size(); j++) {
                char c = words[i][j];
                indegree[c] = 0;
            }
        }

        //Build graph and store indegree.
        for(int i = 0; i < words.size() - 1; i++) {
            string cur = words[i];
            string nex = words[i + 1];
            int len = min(cur.size(), nex.size());
            if(cur.length() > nex.length() && !cur.find(nex))
                return "";
            for(int j = 0; j < len; j++) {
                if(cur[j] != nex[j]) {
                    int sz1 = graph[cur[j]].size();
                    graph[cur[j]].insert(nex[j]); // build graph
                    int sz2 = graph[cur[j]].size();
                    if(sz1 != sz2)
                        indegree[nex[j]]++; // add indegree
                    break;
                }
            }
        }

        //Topo sort using BFS.
        string ans;
        queue<char> q;
        for(auto& e : indegree)
            if(e.second == 0)
                q.push(e.first);

        while(!q.empty()) {
            char cur = q.front();
            q.pop();
            ans += cur;
            for(auto& e : graph[cur])
                if(--indegree[e] == 0)
                    q.push(e);
        }

        //If cyclic, return empty string.
        return ans.length() == indegree.size() ? ans : "";
    }
};