Alien Dictionary.cpp

class Solution {
public:
    string alienOrder(vector<string>& words) {
        vector<pair<int, int>> edges;
        if(!getEdges(words, edges, 0, words.size() - 1, 0))
            return "";
        unordered_map<int, vector<int>> g;
        unordered_map<int, int> indegrees;
        //indegree should contain all nodes
        for(auto& w : words)
            for(auto& c : w)
                indegrees[c] = 0;
        for(auto& e : edges)
        {
            g[e.first].emplace_back(e.second);
            ++indegrees[e.second];
        }
        //get leaves
        queue<int> leaves;
        for(auto& p : indegrees)
            if(!p.second)
                leaves.push(p.first);
        
        //topological sorting
        string res;
        while(leaves.size())
        {
            int size = leaves.size();
            while(size-- > 0)
            {
                int c = leaves.front();
                leaves.pop();
                res += static_cast<char>(c);
                for(auto& next : g[c])
                    if(--indegrees[next] == 0)
                        leaves.push(next);
            }
        }
        //in case there is circle
        return res.size() == indegrees.size()? res: "";
    }

private:
    bool getEdges(vector<string>& words, vector<pair<int, int>>& edges, int lo, int hi, int idx)
    {
        if(lo >= hi)return true;
        unordered_map<int, pair<int, int>> ranges;
        vector<int> seqs;
        for(int i = lo; i <= hi; ++i)
        {
            string w = words[i];
            if(idx >= w.size())
                continue;
            if(ranges.find(w[idx]) == ranges.end())
            {
                ranges[w[idx]] = {i, i};
                seqs.emplace_back(w[idx]);
            }
            else
            {
                //we have a circle here
                if(i - ranges[w[idx]].second > 1)
                    return false;
                ++ranges[w[idx]].second;
            }
        }
        
        //add edges
        for(int i = 0; i + 1 < seqs.size(); ++i)
            edges.emplace_back(seqs[i], seqs[i + 1]);
        
        //recursively process next index
        for(auto& range : ranges)
            if(!getEdges(words, edges, range.second.first, range.second.second, idx + 1))
                return false;
        return true;
    }
};