Introduction

Alien Dictionary is one of the most important applications of Topological Sort.

You are given:

words[]

The words are sorted according to an unknown alien language.

Goal:

Find the order of characters.

If no valid order exists:

Return ""

Example

Input:

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

Output:

wertf

Key Observation

Compare:

Adjacent Words

First different character gives:

Ordering Rule

Example:

wrt
wrf

Difference:

t → f

This becomes a graph edge.

Algorithm

1. Create graph
2. Compare adjacent words
3. Add ordering edges
4. Compute indegrees
5. Perform Topological Sort
6. Build answer

Dry Run

Input:

1. Create graph
2. Compare adjacent words
3. Add ordering edges
4. Compute indegrees
5. Perform Topological Sort
6. Build answer

Edges:

t → fw → e
r → t
e → r

Graph:

w → e → r → t → f

Answer:

wertf

Approach : Topological Sort (Kahn's Algorithm)

Explanation

  1. Extract character ordering.
  2. Build graph.
  3. Calculate indegrees.
  4. Start BFS from indegree 0 characters.
  5. Generate topological ordering.

Practice

Complexity Analysis

Time Complexity: O(C)

Space Complexity: O(U)
C = Total Characters
U = Unique Characters

Why This Problem is Important

  • Topological Sort
  • Graph Construction
  • Kahn's Algorithm
  • Dependency Ordering
  • BFS

Common Beginner Mistakes

  • Comparing all words instead of adjacent words
  • Ignoring invalid prefix case
  • Duplicate edges
  • Wrong graph direction
  • Missing cycle detection

Interview Tip

Always explain:

First differing character creates the graph edge.

That is the entire trick behind Alien Dictionary.

Related Questions

  • Course Schedule
  • Course Schedule II
  • Parallel Courses
  • Sequence Reconstruction

Final Takeaway

Alien Dictionary combines graph construction with Topological Sort.

It teaches:

  • Graph Building
  • Kahn's Algorithm
  • Dependency Resolution
  • Character Ordering

Mastering Alien Dictionary makes advanced graph-ordering interview questions significantly easier.