# 269. Alien Dictionary

Reference: LeetCode
Difficulty: Hard

## Problem

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Note:

• You may assume all letters are in lowercase.
• You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
• If the order is invalid, return an empty string.
• There may be multiple valid order of letters, return any one of them is fine.

Example:

## Analysis

### BFS (Topological Sort)

Note:

• Preprocess: Examine each pair in the words. Try some examples to see how we can gain useful information of a directed edge.
• Set up all the nodes first, then construct the graph.
• Do not add duplicate edges and do not calculate in-degrees for duplicate edges.

Time: $O(NK + V + E)$ where $N$ is the size of words and $K$ is the average length of each word.
Space: $O(V)$

Comment
Junhao Wang
a software engineering cat