Share my 4ms C++ toposort code, beats 92.98% of cpp submissions.


  • 3
    P
    class Solution {
    public:
        string alienOrder(vector<string>& words) {
            if(words.size()==0){
                return "";
            }else if(words.size()==1){
                return words[0];
            }
            bool e[26]={false};
            int in[26]={0};
            vector<vector<int>> E;
            E.resize(26);
            int count=0;
            
            for(int i=0;i<words.size();i++){
                for(int j=0;j<words[i].size();j++){
                    if(!e[words[i][j]-'a']){
                        e[words[i][j]-'a']=true;
                        count++;
                    }
                }
            }
            
            for(int i=1;i<words.size();i++){
                //words[i-1] > words[i]
                int l=min(words[i-1].size(),words[i].size());
                for(int j=0;j<l;j++){
                    //cout<<i<<' '<<j<<endl;
                    if(words[i-1][j]!=words[i][j]){
                        //cout<<words[i-1][j]<<' '<<words[i][j]<<endl;
                        E[words[i-1][j]-'a'].push_back(words[i][j]-'a');
                        in[words[i][j]-'a']++;
                        break;
                    }
                }
            }
        
            string R;
            while(count--){
                bool found=false;
                for(int i=0;i<26;i++){
                    if(e[i]){
                        if(in[i]==0){
                            R.push_back('a'+i);
                            e[i]=false;
                            for(int j=0;j<E[i].size();j++){
                                in[E[i][j]]--;
                            }
                            found=true;
                            break;
                        }
                    }
                }
                if(!found){
                    return "";
                }
            }
            //cout<<R<<endl;
            return R;
        }
    };

Log in to reply
 

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