My 6ms C++ Solution


  • 0
    S
    class Solution {
    public:
        string alienOrder(vector<string>& words) {
            // handle special cases
            if(words.size() == 0) return ""; 
            bool valid = false;
            vector<bool> chars(26, false);
            for(string word: words) {
                for(char c: word) {
                    chars[c-'a'] = true;
                }
            }
            if(words.size() == 1) valid = true;
            if(words.size() == 2 && words[0] == words[1]) valid = true;
            
            
            // construct a directed graph and a reversed graph
            vector<unordered_set<char>> graph(26);
            vector<unordered_set<char>> r_graph(26);
            
            for(int i = 0; i < words.size() - 1; i++) {
                string cur = words[i];
                string next = words[i+1];
                // by comparing the adjacent 2, we can derive some of the characters' orders
                int k = 0;
                // set all the seen chars to be seen;
                while(k<cur.length() && k<next.length() && cur[k] == next[k]) k++;
                if(k<cur.length() && k<next.length()) {
                    valid = true;
                    // construct directed graph and reversed directed graph;
                    graph[cur[k]-'a'].insert(next[k]);
                    r_graph[next[k]-'a'].insert(cur[k]);
                }
            }
            
            if(!valid) return {};
            
            bool has_node = false;
            bool remove1 = false;
            string res = "";
            // topological sort the graph (with cycle):
            while(true) {
                has_node = false;
                remove1 = false;
                for(int i = 0; i < 26; i++) {
                    if(chars[i]) {
                        has_node = true;
                        // check if the current node with 0 in-degree
                        if(r_graph[i].empty()) {
                            remove1 = true;
                            res.push_back('a'+i);
                            // remove all the edges connected to the current node;
                            for(char c : graph[i]) {
                                r_graph[c-'a'].erase('a'+i);
                            }
                            graph[i] = {};
                            // mark current node as removed;
                            chars[i] = false;
                        }
                    }
                }
                // then there is cycle
                if(has_node && !remove1) return {};
                // do until there is no node left in the graph;
                if(!remove1) break;
            }
            return res;
        }
    };
    

Log in to reply
 

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