Simple top sort, Kahn's algorithm


  • 0
    J
    class Solution {
    public:
        string alienOrder(vector<string>& words) {
            vector<vector<int>> g(256);
            vector<int> indegree(256, 0);
            for(int i=1; i < words.size(); i++){
                string w1 = words[i-1];
                string w2 = words[i];
                for(int j=0; j<min(w1.length(), w2.length()); j++){
                    if(w1[j]!=w2[j]){
                        g[w1[j]].push_back(w2[j]);
                        indegree[w2[j]]++;
                        break;
                    }
                }
            }
            
            char res[256];
            int resPos=0;
            queue<int> leaves;
            set<int> seen;
            for(int i=0; i<words.size(); i++){
                for(int j=0; j<words[i].length(); j++){
                    int c = words[i][j];
                    if(seen.count(c) != 0) continue;
                    seen.insert(c);
                    
                    if(indegree[words[i][j]] == 0){
                        leaves.push(words[i][j]);
                    }
                }
            }
            
            while(!leaves.empty()){
                int c = leaves.front(); 
                leaves.pop();
                res[resPos++] = ((char)c);
                
                for(int i=0; i<g[c].size(); i++){
                    int y = g[c][i];
                    indegree[y]--;
                    if(indegree[y] == 0){
                        leaves.push(y);
                    }
                }
            }
            
            if(resPos < seen.size()) return ""; // graph is not a DAG
            
            res[resPos] = '\0';
            return string(res);
        }
    };

Log in to reply
 

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