Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
863 B
0
Indexable
Never
class Solution{
    public:
    string findOrder(string dict[], int n, int k) {
        vector<vector<char>>adj(k);
        vector<int>in(k,0);
        for(int i=1;i<n;i++){
            string s1=dict[i-1], s2=dict[i];
            int j=0;
            while(j<s1.size() && j<s2.size() && s1[j]==s2[j]) j++;
            if(j<s1.size() && j<s2.size()){
                adj[s1[j]-'a'].push_back(s2[j]);
                in[s2[j]-'a']++;
            }
        }
        string res="";
        queue<int>q;
        for(int i=0;i<k;i++){
            if(in[i]==0) q.push(i);
        }
        while(!q.empty()){
            char f=q.front(); q.pop();
            res+=f+'a';
            for(char nbr:adj[f]){
                in[nbr-'a']--;
                if(in[nbr-'a']==0) q.push(nbr-'a');
            }
        }
        //cout<<res<<"\n";
        return res;
    }
};
Leave a Comment