269

269. Alien Dictionary (Hard)

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

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

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 is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

 

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.

Companies:
Facebook, Amazon, Airbnb, Google, Microsoft, Bloomberg, Rubrik, Apple, ByteDance

Related Topics:
Graph, Topological Sort

Similar Questions:

• Course Schedule II (Medium)

Solution 1. Topologic Sort (BFS)

// OJ: https://leetcode.com/problems/alien-dictionary/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    string alienOrder(vector<string>& A) {
        unordered_map<int, unordered_set<int>> G;
        int indegree[26] = {};
        for (auto &s : A) {
            for (char c : s) G[c - 'a'] = {};
        }
        for (int i = 1; i < A.size(); ++i) {
            int j = 0;
            for (; j < min(A[i - 1].size(), A[i].size()); ++j) {
                if (A[i - 1][j] == A[i][j]) continue;
                G[A[i - 1][j] - 'a'].insert(A[i][j] - 'a');
                break;
            }
            if (j == A[i].size() && j < A[i - 1].size()) return "";
        }
        for (auto &[from, tos] : G) {
            for (int to : tos) {
                indegree[to]++;
            }
        }
        queue<int> q;
        for (int i = 0; i < 26; ++i) {
            if (G.count(i) && indegree[i] == 0) q.push(i);
        }
        string ans;
        while (q.size()) {
            int u = q.front();
            q.pop();
            ans += u + 'a';
            for (int v : G[u]) {
                if (--indegree[v] == 0) q.push(v);
            }
        }
        return ans.size() == G.size() ? ans : "";
    }
};

Solution 2. Topological Sort (DFS)

// OJ: https://leetcode.com/problems/alien-dictionary/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    unordered_map<int, unordered_set<int>> G;
    int state[26] = { [0 ... 25] = -1 };
    string ans;
    bool dfs(int u) {
        if (state[u] != -1) return state[u];
        state[u] = 0;
        for (int v : G[u]) {
            if (!dfs(v)) return false;
        }
        ans += 'a' + u;
        return state[u] = 1;
    }
public:
    string alienOrder(vector<string>& A) {
        for (auto &s : A) {
            for (char c : s) G[c - 'a'] = {};
        }
        for (int i = 1; i < A.size(); ++i) {
            int j = 0;
            for (; j < min(A[i - 1].size(), A[i].size()); ++j) {
                if (A[i - 1][j] == A[i][j]) continue;
                G[A[i - 1][j] - 'a'].insert(A[i][j] - 'a');
                break;
            }
            if (j == A[i].size() && j < A[i - 1].size()) return "";
        }
        for (auto &[from, tos] : G) {
            if (!dfs(from)) return "";
        }
        reverse(begin(ans), end(ans));
        return ans.size() == G.size() ? ans : "";
    }
};