3ms C++ solution beats 86%


  • 1
    J
    class Solution {
    public:
        string topoOrder(vector<pair<char, char>>& edges, bool (&open)[26]){
            set<int> adj[26] = { { } };
            int outs[26] = { 0 };
            set<int> leaves;
            int numOfChars = 0;
            
            for(auto e: edges){
                int from = e.first - 'a';
                int to = e.second - 'a';
                if (adj[to].find(from) == adj[to].end()) {
                    adj[to].insert(from);
                    ++outs[from];
                }
            }
            
            for(int i = 0; i < 26; i++) {
                if (open[i]) {
                    numOfChars++;
                    if (outs[i] == 0) leaves.insert(i);
                }
            }
            
            deque<char> s;
            while(!leaves.empty()){
                set<int> newLeaves;
                for(auto leaf: leaves){
                    for(auto from: adj[leaf]){
                        if (--outs[from] == 0)
                            newLeaves.insert(from);
                    }
                    s.push_front('a' + leaf);
                }
                leaves = newLeaves;
            }
    
            if (s.size() != numOfChars) return "";
            return string(s.begin(), s.end());
        }
        void buildOpenSet(bool (&open)[26], string& word){
            for(auto c : word)
                open[c - 'a'] = true;
        }
        string alienOrder(vector<string>& words) {
            vector<pair<char, char>> edges;
            bool open[26] = {false};
            for(int i = 0; i < words.size(); i++)
                buildOpenSet(open, words[i]);
    
            for(int i = 0; i < words.size() - 1; i++){
                auto pre = words[i];
                auto next = words[i + 1];
                int len = min(pre.size(), next.size());
                int pos;
                for(pos = 0; pos < len && pre[pos] == next[pos]; pos++);
                if (pos < pre.size()) {
                    if (pos == next.size()) return "";
                    edges.push_back(make_pair(pre[pos], next[pos]));
                }
            }
            
            return topoOrder(edges, open);
        }
    };
    

Log in to reply
 

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