Alien Dictionary

Explanation & Solution

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, where the strings are sorted lexicographically by the rules of this new language.

Derive the order of letters in this language. If the order is invalid, return "". If there are multiple valid orderings, 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 only if s.length < t.length.

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

wrt

wrf

ett

rftt

Output: "wertf"

Explanation: From the words we can derive: w comes before e, e before r, t before f, r before t. This gives the order "wertf".

Constraints

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

Approach

Topological Sort pattern

1. Initialize the Graph

Create a directed graph and in-degree map for every unique character across all words
Each character is a node; edges will represent ordering constraints

2. Extract Ordering Rules from Adjacent Words

Compare each consecutive pair of words character by character
The first differing character gives us an edge: w1[j] → w2[j] (w1's char comes before w2's char)
If w1 is a prefix of w2 but longer, the input is invalid — return ""
Only the first difference matters; stop comparing after finding it

3. BFS Topological Sort (Kahn's Algorithm)

Enqueue all characters with inDegree === 0
Dequeue a character, append to result, and decrement in-degree of its neighbors
Enqueue neighbors whose in-degree drops to 0

4. Validate the Result

If the result contains all unique characters, a valid order exists — return it as a string
If some characters remain (cycle detected), return ""

Key Insight

The alien dictionary defines a partial order on characters, which maps directly to a directed graph
Comparing adjacent words gives us edges, and topological sort produces a valid total ordering
Using a Set for adjacency prevents duplicate edges that would corrupt in-degree counts
The prefix check ("abc" before "ab") catches an edge case that violates lexicographic rules

Time

O(C) where C is the total number of characters across all words

Space

O(U + E) where U is unique characters and E is the number of ordering edges

Solution Code

Course Schedule II

Compilation Order