Description

Submission

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> next;
        unordered_map<char, int> inDegree;

        for(auto word : words) {
            for(auto ch : word) {
                inDegree[ch] = 0;
            }
        }


        for(int i = 0; i < words.size() - 1; ++i) {
            string s = words[i];
            string t = words[i+1];
            if(s.size() > t.size() && s.substr(0, t.size()) == t) return "";
            for(int j =0; j < min(s.size(), t.size()); ++j) {
                if(s[j] == t[j]) continue;
                if(next[s[j]].find(t[j]) == next[s[j]].end()) {
                        next[s[j]].insert(t[j]);
                        inDegree[t[j]]++;
                }
                break;
            }
        }

        queue<char> q;
        for(auto p: inDegree) {
            if(p.second == 0) {
                q.push(p.first);
            }
        }

        string ret = "";
        while(!q.empty()) {
            auto ch = q.front();
            ret.push_back(ch);
            q.pop();

            for(auto p : next[ch]) {
                inDegree[p]--;
                if(inDegree[p] == 0) q.push(p);
            }
        }

        if(ret.size() != inDegree.size()) return "";
        return ret;

    }
};

References

1. https://www.youtube.com/watch?v=yfGJFDkyEmE