A C++ soution with explanations, build graph + topological sort


  • 0
    class Solution{
    private:
    	int inline getIndex(char c){
    		return (int)(c - 'a');
    	}
    public:
    	string alienOrder(vector<string>& words) {
    		string result;
    		if(words.size() <= 1){
    			return result;
    		}
    		
    		unordered_set<char> zeroInDegreeChars;
    		// First, we assume there is no relationship between chars, so every char has 0 indegree.
    		vector<unordered_set<char>> charIndgrees(26, unordered_set<char>());
    		for(auto w : words){
    			for(auto c : w){
    				zeroInDegreeChars.insert(c);
    			}
    		}
    		
    		// Build indgree graph.
    		// For example, if we met "ad" then "ab", we know 'd' < 'b'
    		// To record this, we add d to b's precedent char set, which means d points to b.
    		// Meanwhile, we remove b from the zeroInDegreeChars set, since now it has a precedence.
    		for(size_t i = 1; i < words.size(); i++){
    			string w1 = words[i-1], w2 = words[i];
    			size_t len = min(w1.size(), w2.size());
    			for(size_t j = 0; j < len; j++){
    				if(w1[j] != w2[j]){
    					char c1 = w1[j], c2 = w2[j];
    					zeroInDegreeChars.erase(c2);
    					charIndgrees[getIndex(c2)].insert(c1);
    				}
    			}
    		}
    		
    		// Do topology sort, every time, pick up a 0 indegree char.
    		while(!zeroInDegreeChars.empty()){
    			char c = *(zeroInDegreeChars.begin());
    			result += c;
    			zeroInDegreeChars.erase(c);
    			// Remove c from the precedence sets of other chars.
    			for(size_t i = 0; i < charIndgrees.size(); i++){
    				auto indgreeSet = charIndgrees[i];
    				if(!indgreeSet.empty()){
    					if(indgreeSet.find(c) != indgreeSet.end()){
    						indgreeSet.erase(c);
    						// If c is the only precedence of current char, 
    						// we can add current char to zeroInDegreeChars now.
    						if(indgreeSet.empty()){
    							zeroInDegreeChars.insert((char)(i + 'a'));
    						}
    					}
    				}
    			}
    		}
    		
    		return result;		
    	}
    };
    

    Tested with a few cases but haven't tested with the OJ system.


Log in to reply
 

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