8ms C++ Solution


  • 0
    G
    class Solution {
    public:
    	string alienOrder(vector<string>& words) 
    	{
    		if (words.size() ==0) return "";
    
    		unordered_map<char, int> ingress;
    
    		for (auto& w : words)
    		{
    			for (auto& ch : w)
    			{
    				ingress[ch];
    			}
    		}
    
    		vector<pair<char, char>> pairs;
    		for (int i = 0; i < words.size() - 1; i++)
    		{
    			pair<char, char> p;
    			if (scan(words[i], words[i + 1], p))
    			{
    				pairs.push_back(p);
    			}
    		}
    
    		for (auto& p : pairs)
    		{
    			if (ingress.find(p.second) == ingress.end()) ingress[p.second] = 1;
    			else ingress[p.second]++;
    		}
    
    		stack<char> stack;
    		for (unordered_map<char, int>::iterator iter = ingress.begin(); iter != ingress.end(); iter++)
    		{
    			if (iter->second == 0) stack.push(iter->first);
    		}
    
    		if (stack.size() == 0 && stack.size() > 1) return "";
    
    		string ret;
    		while (stack.size() > 0)
    		{
    			char top = stack.top();
    			stack.pop();
    			ret += top;
    
    			for (auto& p : pairs)
    			{
    				if (p.first == top)
    				{
    					ingress[p.second]--;
    					if (ingress[p.second] == 0) stack.push(p.second);
    				}
    			}
    		}
    
    		for (unordered_map<char, int>::iterator iter = ingress.begin(); iter != ingress.end(); iter++)
    		{
    			if (iter->second != 0) return "";
    		}
    
    		return ret;
    	}
    
    	bool scan(string w1, string w2, pair<char, char>& p)
    	{
    		int k = 0;
    		while (k < w1.size() && k < w2.size() && w1[k] == w2[k]) k++;
    		if (k < w1.size() && k < w2.size())
    		{
    			p.first = w1[k];
    			p.second = w2[k];
    			return true;
    		}
    
    		return false;
    	}
    };

Log in to reply
 

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