Skip to content

Alien Dictionary⚓︎

Link

Description⚓︎

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language.

A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alien language than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one.

If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".

Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there are multiple solutions, return any of them.

Example 1:

  • Input: words = ["wrt","wrf","er","ett","rftt"]
  • Output: "wertf"

Example 2:

  • Input: words = ["z","x"]
  • Output: "zx"

Example 3:

  • Input: words = ["z","x","z"]
  • Output: ""
  • Explanation: The order is invalid, so return "".

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of only lowercase English letters.

Solution⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    string alienOrder(vector<string>& words) {
        vector<int> inDegree(26, -1);
        for (const string& word : words) {
            for (const char& ch : word)
                inDegree[ch - 'a'] = 0;
        }

        vector<vector<int>> edges(26);
        for (int i = 0; i < words.size() - 1; i++) {
            string currentWord = words[i], nextWord = words[i + 1];
            int len = min(currentWord.length(), nextWord.length());
            int j = 0;
            for (j = 0; j < len; j++) {
                if (currentWord[j] != nextWord[j]) {
                    edges[currentWord[j] - 'a'].push_back(nextWord[j] - 'a');
                    inDegree[nextWord[j] - 'a']++;
                    break;
                }
            }
            if (j < currentWord.length() && j == nextWord.length())  // handle ["abc","ab"] case
                return "";
        }

        queue<int> que;
        int count = 0;
        for (int i = 0; i < 26; i++) {
            if (inDegree[i] != -1)
                count++;
            if (inDegree[i] == 0)
                que.push(i);
        }

        string res;
        while (!que.empty()) {
            int current = que.front();
            que.pop();
            res.push_back(static_cast<char>(current + 'a'));
            for (int v : edges[current]) {
                if (--inDegree[v] == 0)
                    que.push(v);
            }
        }

        return res.size() == count ? res : "";
    }
};
  • Time complexity: \(O(C)\), where \(C\) is the total length of all the words in the input list, added together;
  • Space complexity: \(O\left( U+\min \left( U^2,N \right) \right) \approx O\left( 1 \right)\), where \(N\) is the total number of strings in the input list, and \(U\) is the total number of unique letters in the alien alphabet (in this case is \(26\) ).