題目網址：https://leetcode.cn/problems/alien-dictionary/

題意：有一種使用英文的外星語言, 其字母的順序與英文的順序不同。

給一 word list words 作為該外星語言的字典, wrods 中的 string 已按照外星語言的字母順序進行排序。

請按照 words 還原出該語言中已知的字母順序, 並按字母的遞增順序排列。若不存在合法的字母順序, 則返回 ""。若存在多種合法的順序, 則返回任意一種即可。

string s 小於 string t 有兩種情況:

  • 在第一個不同的字母處, s 的字母順序在 t 的字母之前
  • 如果前 min(s.length, t.length) 個字母都相同, 且 s.length < t.length

words[i] 僅由小寫字母組成。

Solution：

想法：利用 Topological Sort + BFS, 類似 207. Course Schedule, 相鄰兩個 word 可建構一條順序

e.g. words = ["wrt","wrf","er","ett","rftt"]

  • 取 wrt 和 wrf ➔ 得 t < f

  • 取 wrf 和 er ➔ 得 w < e

  • 取 er 和 ett ➔ 得 r < t

  • 取 ett 和 rftt ➔ 得 e < r

最終得 w < e < r < t < f

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> adj; // adjacency list
        unordered_map<char, int> inDegree; // 紀錄每個 char 的 in degree

        // 將所有會出現的 char 的 in degree 設成 0
        // 因為有解的話會有 char 的 in degree = 0
        // 若不在這邊設成 0 的話, 到時候初始化 q 時會取不出 char
        for (const auto& word : words) {
            for (const auto& ch : word) {
                inDegree[ch] = 0;
            }
        }

        // 每次取出兩個 string 來比較, 並建構 char 的順序
        for (int i = 0; i < words.size() - 1; ++i) {
            const int m = s.size(), n = t.size();
            const string s = words[i], t = words[i + 1];

            // words 中 s 的順序在 t 之前, 且 s 包含 t
            // 不合 s < t 的第二條規則, 照理來說 t 應放在 s 之前(words 中給的順序是錯的)
            if (m > n && s.substr(0, n) == t) {
                return "";
            }

            for (int j = 0; j < min(m, n); ++j) {
                const int c1 = s[j], c2 = t[j];

                if (c1 == c2) {
                    continue; // 若 char 相同則跳過, 去比較下一個 char
                }

                // 若不相同, 則 check c1 的 adj list 中是否已經有紀錄 c2
                // 若沒有, 則要把 c2 加入到 c1 的 adj list 中, 並將 c2 的 in degree + 1
                if (adj[c1].find(c2) == adj[c1].end()) {
                    adj[c1].emplace(c2);
                    ++inDegree[c2];
                }

                // 比較完第一個不同的 char 之順序後, 便跳出
                break;
            }
        }

        // 取出 in degree = 0 之 char 來初始化 q
        queue<char> q;
        for (const auto& [ch, degree] : inDegree) {
            if (degree == 0) {
                q.emplace(ch);
            }
        }

        // bfs
        string res;
        while (!q.empty()) {
            const auto cur = q.front();
            q.pop();
            res += cur;

            // 把 cur 給 pop 掉後, 將 cur 的 adjacent vertex 之 in degree - 1
            for (const auto& v : adj[cur]) {
                if (--inDegree[v] == 0) {
                    q.emplace(v);
                }
            }
        }

        // 若 res 的長度 < words 中 char 的個數, 代表有 char 的 in degree 無法變成 0
        // 也就是說存在 cycle, 故返回 ""
        return res.size() < inDegree.size() ? "" : res;
    }
};
  • time：$O(n \cdot L)$ ➔ $O(n \cdot L) + O(26 + n)$
    • $O(n \cdot L)$：建立 inDegree 需遍歷 words 中的每個 char
      • 其中 n 為 words 的個數, L 為每個 word 的平均長度
    • $O(26 + n)$：$O(V + E)$ 也就是 BFS 的時間複雜度
      • edge 最多 n - 1 條（相鄰 2 個 word 建構一個字母順序）
      • vertex 最多 26 個, 因為 inDegree 最多紀錄 26 個 char 的 in degree
  • space：$O(n)$ ➔ $O(26 + n)$
    • $O(26 + n)$：$O(V + E)$ 為 adj 所需的空間, 其中 n 為 words 的個數
      • edge 最多 n - 1 條（相鄰 2 個 word 建構一個字母順序）
      • vertex 最多 26 個, 因為 inDegree 最多紀錄 26 個 char 的 in degree