【图论之拓扑排序】剑指 Offer II 114. 外星文字典

剑指 Offer II 114. 外星文字典

讲解传送门

const int N = 26, M = N * N;
class Solution {
public:
    int h[N], e[M], ne[M], idx = 0;
    bool st[N];
    int in[N], cnt = 0; // 上面三行要写在class Solution内部，不然每次调用不会清空
    void add(int a, int b)
    {
        e[idx] = b, ne[idx]= h[a], h[a] = idx ++ ;
    }

    bool build(string s, string t)
    {
        int n = min(s.size(), t.size());
        for (int i = 0; i < n; i ++ )
        {
            int a = s[i] - 'a', b = t[i] - 'a';
            if (a != b) 
            {
                add(a, b);
                in[b] ++ ;
                return true;
            }
        }
        return s.size() <= t.size(); // 必须要等号，因为字典里有两个一样的串也算构建成功
    }

    string alienOrder(vector<string>& words) {
        memset(h, -1, sizeof h);    
        int n = words.size();
        string res = "";
        for (int i = 0; i < n; i ++ )
        {
            for (auto c: words[i])
            {
                if (!st[c - 'a'])
                {
                    cnt ++ ;
                    st[c - 'a'] = true;
                }
            }
            for (int j = 0; j < i; j ++ )
            {
                if (!build(words[j], words[i])) 
                    return "";
            }
        }
        queue<int> q;
        for (int i = 0; i < 26; i ++ )
        {
            if (!in[i] && st[i])
                q.push(i);
        }
        while (q.size())
        {
            int t = q.front();
            q.pop();
            res += (char)(t + 'a');
            for (int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                if (-- in[j] == 0)
                    q.push(j);
            }
        }
        return cnt == res.size() ? res : "";
    }
};