269. 火星辭典

思路

• 因為字串都已經排序好，只需要比較相鄰的兩個字串就好。

「會不會有一種情況，相隔很遠的兩個字串，能提供相鄰字串提供不了得字母關係？」
這是不可能的。

因為在一個排序好的陣列中，如果words[i]和words[i+2]在 $index=k$ 的地方有不同的字母，
那麼夾在中間的words[i+1]，在 $index=0\sim{k-1}$ 的前綴必定長的一模一樣。
因此，words[i]和words[i+2]在位置 $k$ 的大小關係，
一定會被包含在words[i], words[i+1]或words[i+1], words[i+2]的比較當中。
跨字串比較不會產生任何「全新」的邏輯。

1. 先找出所有存在的字元，隨後在比較時按照題目給定的規則，建立入度表跟鄰接表。
2. 用拓樸排序的方法，找出每個字元的大小順序。

程式碼

拓樸排序

class Solution {
public:
    string alienOrder(vector<string>& words) {
        const int MX = 26;
        vector<vector<int>> graph(MX);
        int indegree[MX];
        ranges::fill(indegree, -1);
        for(string& s : words) { // 紀錄那些字元有出現過，後面會用到
            for(char& c : s) {
                indegree[c - 'a'] = 0;
            }
        }
        int j, len;
        for(int i = 0; i < words.size() - 1; i++) {
            string cur = words[i];
            string nxt = words[i + 1];
            j = 0;
            len = min(cur.length(), nxt.length());
            while(j < len) {
                if(cur[j] != nxt[j]) { // 找到第一個不同的位置，此時兩字元有大小關係。
                    graph[cur[j] - 'a'].push_back(nxt[j] - 'a');
                    indegree[nxt[j] - 'a']++;
                    break;
                }
                j++;
            }
            if(j < cur.length() && j == nxt.length()) { 
                // 前面都相同，但字典序較大的字串卻比較靠後，比如 adcd, abc, 不可能
                return "";
            }
        }
        int q[MX]; // 最多只有 26 個元素
        int l = 0, r = 0;
        int kinds = 0;
        for(int i = 0; i < MX; i++) {
            if(indegree[i] != -1) { // -1 表示不存在
                kinds++;
            }           
            if(indegree[i] == 0) { // 將入度為 0 的元素加入
                q[r++] = i;
            }
        }
        string res;
        while(l != r) {
            int cur = q[l++];
            res += (char)(cur + 'a');
            for(int neighbor : graph[cur]) {
                if(--indegree[neighbor] == 0) {
                    q[r++] = neighbor;
                }
            } 
        }
        return res.length() == kinds ? res : "";
    }
};

複雜度分析

• 時間複雜度：$O(nL+|\small{\sum}|)$，$L$代表字串平均長度，$\small{\sum}$ 是字典的字母集合。
• 空間複雜度：$O(n+|\small{\sum}|)$