c++ topological sorting


  • 0
    Z
    class Solution {
    public:
        string alienOrder(vector<string>& words) {
            vector<int> g[26];
            int in[26] = {0};
            bool vis[26] = {false};
            int count = 0;
            for (auto &s : words) {
                for (auto &c : s) {
                    vis[c - 'a'] = true;
                }
            }
            for (int i = 0; i < 26; i++) {
                count += vis[i];
            }
            for (int i = 0; i < words.size() - 1; i++) {
                string &s1 = words[i], &s2 = words[i + 1];
                for (int j = 0; j < s1.size() && j < s2.size(); j++) {
                    if (s1[j] == s2[j]) continue;
                    g[s1[j] - 'a'].push_back(s2[j] - 'a');
                    in[s2[j] - 'a']++;
                    break;
                } 
            }
            queue<int> que;
            string res = "";
            for (int i = 0; i < 26; i++) {
                if (vis[i] && in[i] == 0) {
                    que.push(i);
                }
            }
            
            while (!que.empty()) {
                int cur = que.front();
                que.pop();
                res += (char)('a' + cur);
                for (auto & v: g[cur]) {
                    in[v]--;
                    if (in[v] == 0) que.push(v);
                }
            }
            
            if (res.size() != count) return "";
            
            return res;
        }
    };
    
    

Log in to reply
 

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