Simple topological sort based 3ms solution


  • 0
    A
    class Solution {
    public:
        vector<int> adj[128];
        int col[128];
        string out;
        unordered_set<int> uset;
        bool HasCycle(int u) {
            col[u] = 1;
            for (auto v : adj[u]) {
                if (col[v] == 1) return true;
                else if (!col[v] && HasCycle(v)) return true;
            }
            col[u] = 2;
            out.push_back(u);
            uset.erase(u);
            return false;
        }
        string alienOrder(vector<string>& words) {
            for (int i = 0; i < words.size(); ++i) {
                for (int j = 0; j < words[i].size(); ++j) {
                    if (i + 1 < words.size() && j < words[i + 1].size() && words[i][j] != words[i + 1][j] && 
                    (j == 0 || words[i][j - 1] == words[i + 1][j - 1])) adj[words[i][j]].push_back(words[i + 1][j]);
                    uset.insert(words[i][j]);
                }
            }
            for (int i = 'a'; i <= 'z'; ++i) {
                if (!col[i] && adj[i].size()) {
                    if (HasCycle(i)) return "";
                }
            }
            for (auto v : uset) out += v;
            return string(out.rbegin(), out.rend());
        }
    };
    

Log in to reply
 

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