Alien Dictionary

There is a foreign language which uses the latin alphabet, but the order among letters is not "a", "b", "c" ... "z" as in English.

You receive a list of non-empty strings words from the dictionary, where the words are sorted lexicographically based on the rules of this new language.

Derive the order of letters in this language. If the order is invalid, return an empty string. If there are multiple valid order of letters, return any of them.

A string a is lexicographically smaller than a string b if either of the following is true:

• The first letter where they differ is smaller in a than in b.
• a is a prefix of b and a.length < b.length.

From "z" and "o", we know 'z' < 'o', so return "zo".

• from "hrn" and "hrf", we know 'n' < 'f'
• from "hrf" and "er", we know 'h' < 'e'
• from "er" and "enn", we know get 'r' < 'n'
• from "enn" and "rfnn" we know 'e' < 'r'
• so one possible solution is "hernf"

Approach

Build a graph of character precedence by comparing adjacent words and finding the first differing character. Add a directed edge from the earlier word's character to the later word's character, and track indegrees. If a word is a prefix of a previous longer word, return empty. Then perform topological sort; if all characters are included, return the ordering.

Why It Works

The first differing character between adjacent words defines an ordering constraint that must hold in any valid alphabet. Topological sorting produces an order that satisfies all constraints, and any cycle implies no valid ordering. The prefix check handles invalid cases not captured by edges.

Complexity

• Time: O(total characters)
• Space: O(total unique characters)

Reference Implementation (Python)

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = {ch: set() for word in words for ch in word}
        indeg = {ch: 0 for ch in graph}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            if len(w1) > len(w2) and w1.startswith(w2):
                return ""
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        indeg[c2] += 1
                    break

        queue = deque([ch for ch in indeg if indeg[ch] == 0])
        order = []
        while queue:
            ch = queue.popleft()
            order.append(ch)
            for nei in graph[ch]:
                indeg[nei] -= 1
                if indeg[nei] == 0:
                    queue.append(nei)

        if len(order) != len(indeg):
            return ""
        return "".join(order)