269. Alien Dictionary

build graph O(mn) time
topological sort O(v+e) time
这里[“ab”, “abc”]以及[“z”, “z”]都是合法的，返回任一结果即可，但是[“abc”, “ab”]是非法的，必须返回空串

class Solution {
public:
    string alienOrder(vector<string>& words) {
        string u;
        for (auto v : words) { // 这个必须是deep copy因为后边要修改
            for (auto c : v) {
                if (!g.count(c)) {
                    g[c] = {}; // 需要对unordered_set初始化否则结果不完整会丢字符
                }
            }
            int n = min(u.length(), v.length()), i = 0;
            for (; i < n; ++i) { // 比较前后两个字符串的每个字符，如果发现不一样的加一条边
                if (u[i] != v[i]) {
                    g[u[i]].insert(v[i]);
                    break;
                }
            }
            if (i == n && u.length() > v.length()) return ""; // ["abc", "ab"]非法
            u.swap(v);
        }
        visited.resize(128);
        for (auto [c, _] : g) {
            if (!isAcyclic(c)) return "";
        }
        return string(rbegin(s), rend(s));
    }

    bool isAcyclic(char u) {
        if (visited[u]) return visited[u] == 1;
        visited[u] = -1;
        for (auto v : g[u]) {
            if (!isAcyclic(v)) return false;
        }
        s += u;
        visited[u] = 1;
        return true;
    }

    string s;
    unordered_map<char, unordered_set<char>> g; // 用unordered_set去重
    vector<char> visited; // -1 0 1节省空间
};

class Solution {
public:
    string alienOrder(vector<string>& words) {
        if (words.size() == 1) return words[0];
        auto cmp = [](const string &a, const string &b) {return a.length() < b.length();};
        int n = words.size(), m = max_element(begin(words), end(words), cmp)->length();
        vector<bool> isOrdered(n - 1);
        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < n - 1; ++i) {
                if (!isOrdered[i]) {
                    if (words[i].length() <= j) {
                        isOrdered[i] = true;
                    } else if (words[i][j] != words[i + 1][j]) {
                        isOrdered[i] = true;
                        g[words[i][j]].insert(words[i + 1][j]);
                        if (g.count(words[i + 1][j]) == 0) {
                            g[words[i + 1][j]] = {};
                        }
                    }
                }
                if (j < words[i].length() && g.count(words[i][j]) == 0) {
                    g[words[i][j]] = {};
                }
                if (j < words[i + 1].length() && g.count(words[i + 1][j]) == 0) {
                    g[words[i + 1][j]] = {};
                }
            }
        }
        visited.resize(128);
        for (auto &&p : g) {
            if (!ts(p.first)) return "";
        }
        string res;
        while (!s.empty()) {
            res += s.top();
            s.pop();
        }
        return res;
    }

    bool ts(char ch) {
        if (visited[ch] == 1) return true;
        if (visited[ch] == -1) return false;
        visited[ch] = -1;
        for (auto &&c : g[ch]) {
            if (!ts(c)) return false;
        }
        s.push(ch);
        visited[ch] = 1;
        return true;
    }

    vector<int> visited;
    stack<char> s;
    unordered_map<char, unordered_set<char>> g;
};

followup: All results of Alien Dictionary

class Solution {
public:
    vector<string> alienOrder(vector<string> words) {
        string u;
        for (auto v : words) {
            for (char c : v) {
                if (g.count(c) == 0) {
                    g[c] = {};
                }
            }
            int len = min(u.length(), v.length()), i = 0;
            for (; i < len; ++i) { // 比较前后两个字符串的每个字符，如果发现不一样的加一条边
                if (u[i] != v[i]) {
                    g[u[i]].insert(v[i]);
                    break;
                }
            }
            if (i == len && u.length() > v.length()) return {}; // ["abc", "ab"]非法
            u.swap(v);
        }
        n = g.size();
        visited.resize(128);
        dfs(0);
        return res;
    }

    void dfs(int b) {
        if (b == n) {
            res.push_back(s);
            return;
        }
        for (auto [c, _] : g) {
            if (visited[c] || !isValid(c)) continue;
            visited[c] = true;
            s += c;
            dfs(b + 1);
            s.pop_back();
            visited[c] = false;
        }
    }

    bool isValid(char c) {
        for (char t : s) {
            if (g[c].count(t)) return false;
        }
        return true;
    }

    int n;
    vector<bool> visited;
    string s;
    vector<string> res;
    unordered_map<char, unordered_set<char>> g;
};

int main() {
    Solution sol;
    for (auto s : sol.alienOrder({"wrt","wrf","er","ett","rftt"})) {
        cout<<s<<endl;
    }
    return 0;
}