Hard

Alien Dictionary

LAB

Given words sorted by an unknown alphabet, return the lexicographically smallest valid character order. Return an empty string if no valid order exists.

EXAMPLES

Example 1

Input
{
  "words": [
    "wrt",
    "wrf",
    "er",
    "ett",
    "rftt"
  ]
}

Output
"wertf"

FUNCTION SHAPE

words: stringArray→string

SOLUTION NOTE

This is an interesting application for topological sort. It can be tricky to realize we can model this problem as a graph. The intuition is that dictionary ordering can be described as enforcing a graph relationship. For example, the alphabetical ordering of 'abcdef'...' can be represented as a graph of 26 nodes for each letter, with directed edges from a->b, b->c, and so on, meaning that a comes before b… Note that a comes before c, but we don't need a direct edge connecting a->c, since we get that relationship transitively from a->b and b->c. This will improve our efficiency from O(letters^2) to O(letters).

You want to think about the regular english language. When comparing two words, how do you tell if one comes later than the other in the dictionary? You compare letter by letter left to right. At the first difference, the word with the earlier letter comes earlier. If there is no difference, but one is longer, the shorter one comes earlier. We just need to simulate this process, and at the first difference, (a != b) we know that this character a is earlier than the other character b causes the word to be ordered before the other one. So there must be the edge a -> b in this alien dictionary.

You may be asking, why not use Counter() or defaultdict(int) for in_degree? It's generally better to concretely define in_degree for all nodes in the graph, otherwise the queue can be empty, because the keys are not in there.

Reveal reference solution +

pythonREFERENCE

from collections import defaultdict, deque
def alienOrder(self, words):
    # Step 1: Initialize graph
    graph = defaultdict(set)
    in_degree = {char: 0 for word in words for char in word}

    # Step 2: Build the graph
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        if w1[:min_len] == w2[:min_len] and len(w1) > len(w2):
            return ""  # Invalid order
        for c1, c2 in zip(w1, w2):
            if c1 != c2:
                if c2 not in graph[c1]:
                    graph[c1].add(c2)
                    in_degree[c2] += 1
                break

    # Step 3: Topological sort using BFS
    queue = deque([c for c in in_degree if in_degree[c] == 0])
    result = []

    while queue:
        char = queue.popleft()
        result.append(char)
        for neighbor in graph[char]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) < len(in_degree):
        return ""  # Cycle detected
    return "".join(result)

TimeO(C)

SpaceO(1)

Open on LeetCode ↗