Extremely clear and clean version of topological sort


  • 0
    X
    class Solution {
    public:
        string alienOrder(vector<string>& words)
        {
        	map<char, set<char>> indeg, outdeg;
        	set<char> pool;
        	for (int i=0;i<words.size();i++)
        	{
        		pool.insert(words[i].begin(),words[i].end());
        		for (int j = 0; i>0&&j < min(words[i].size(),words[i-1].size()); j++)
        		{
        			if (words[i][j]!=words[i-1][j])
        			{
        				indeg[words[i][j]].insert(words[i - 1][j]);
        				outdeg[words[i - 1][j]].insert(words[i][j]);
        				break;
        			}
        		}
        	}
        
            string res;
        	int len = pool.size();
        	for (auto it : indeg)
        		pool.erase(it.first);
        	while (!pool.empty())
        	{
        		char curr = *pool.begin();
        		pool.erase(curr);
        		res += curr;
        		for (char next : outdeg[curr])
        		{
        			indeg[next].erase(curr);
        			if (indeg[next].empty())
        				pool.insert(next);
        		}
        	}
        	return res.size() == len ? res : "";
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.