DAY 14 試題

(由於此題為上鎖題，因此題目只能從網路分享看到)

問題描述

給定一個外星語言的字典，字典中的單詞按照外星語言的字母順序進行排序。儘管字典使用的是拉丁字母，但字母之間的順序是未知的。我們的目標是根據給定的單詞列表，推導出這個外星語言中字母的排列順序。如果有多種有效的字母順序，我們只需返回其中一種。如果發現字典中的順序無效，則返回空字串。

例 1：
輸入： ["wrt", "wrf", "er", "ett", "rftt"]
輸出： "wertf"

例 2：
輸入： ["z", "x"]
輸出： "zx"

解題思路

這道題本質上是圖論中的拓撲排序問題。我們將字母看作圖中的節點，字母之間的順序關係看作有向邊。我們首先需要構建這個有向圖，然後利用拓撲排序的算法來找出字母的排列順序。步驟如下：

1. 構建有向圖：通過比較相鄰的單詞，找到它們之間的字母先後順序，並構建字母之間的有向邊。對於每一對相鄰單詞，找到第一個不同的字母，並設置從前一個字母指向後一個字母的邊。
2. 計算入度：為每個字母計算其入度，入度表示有多少個字母必須在它之前出現。初始時，所有不需要在其他字母之後的字母入度為 0。
3. 拓撲排序：使用廣度優先搜索 (BFS) 來對字母進行排序。首先選擇所有入度為 0 的字母，將它們加入結果中。然後遍歷這些字母，並將它們對應的有向邊移除，更新其他字母的入度。最終，如果所有字母都被訪問過，則順序有效；否則圖中存在環，無法找到有效的字母順序。

class Solution {
 public:
     string alienOrder(vector<string>& words) {
         set<pair<char, char>> st;  // 用來存儲字母間的順序關係
         unordered_set<char> ch;    // 用來存所有出現的字母
         vector<int> in(256, 0);    // 入度表
         queue<char> q;             // 拓撲排序隊列
         string res;                // 最終結果字串

         // 初始化：把所有出現過的字母加入集合
         for (auto a : words) 
             ch.insert(a.begin(), a.end());

         // 比較相鄰單詞，找到字母之間的順序關係
         for (int i = 0; i < (int)words.size() - 1; ++i) {
             int mn = min(words[i].size(), words[i + 1].size()), j = 0;
             for (; j < mn; ++j) {
                 if (words[i][j] != words[i + 1][j]) {
                    st.insert(make_pair(words[i][j], words[i + 1][j]));
                     break;
                }
            }
            // 檢查無效順序的情況，例如當前一個單詞是後一個單詞的前綴
            if (j == mn && words[i].size() > words[i + 1].size()) 
                return "";
        }

        // 計算每個字母的入度
        for (auto a : st) 
            ++in[a.second];

        // 將所有入度為 0 的字母加入隊列
        for (auto a : ch) {
             if (in[a] == 0) {
                q.push(a);
                res += a;
            }
        }

        // 拓撲排序
        while (!q.empty()) {
             char c = q.front(); 
             q.pop();
             
             for (auto a : st) {
                 if (a.first == c) {
                     --in[a.second];
                     if (in[a.second] == 0) {
                        q.push(a.second);
                        res += a.second;
                    }
                }
            }
        }

        // 檢查排序結果是否包含所有字母，否則返回空字串
        return res.size() == ch.size() ? res : "";
    }
};

解法重點與分析

這道題的核心重點在於如何通過圖論中的拓撲排序來處理字母的排列順序。首先，構建一個有向圖，然後使用入度表來進行拓撲排序。若排序成功，說明字母順序有效；如果存在環，則無法找到有效的順序。

時間複雜度
圖的構建和拓撲排序的時間複雜度是 O(N + E)，其中 N 是字母的數量，E 是圖中邊的數量。具體來說，我們需要遍歷所有單詞來比較字母的順序，並對圖進行排序，因此這是圖論問題中的常見時間複雜度。

總結

這題考察的是如何根據給定的字母順序規則構建有效的字母排列。通過比較字典中相鄰的單詞，逐步確定字母之間的相對順序，並利用拓撲排序處理字母之間的依賴關係。通過構建有向圖，我們可以將入度為零的字母按順序加入結果中，並依次移除相應的依賴關係。若最後結果中包含所有字母，則表示排序有效，否則說明順序無效。此題的時間複雜度為 O(N + E)，空間複雜度也取決於圖的結構。

以上是第十四天的自學內容分享，謝謝大家。