Alien Dictionary

Asked byFacebookAirbnbAmazonGoogleBloombergUber

Problem

There is a foreign language that uses the English alphabet but with a different sort order. Given a list of words already sorted according to that alien language's rules, derive and return one valid ordering of the letters used, or an empty string if no valid order exists.

Examples

Example 1

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

Output:"wertf"

Example 2

Input:words = ["z","x","z"]

Output:""

The order is contradictory.

Constraints

1 <= words.length <= 100

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Advanced Graphs pattern

Beyond basic traversal, some graph problems need ordering constraints (topological sort) or weighted shortest paths (Dijkstra, Bellman-Ford, minimum spanning trees).

Look for this pattern when

The problem has ordering or prerequisite constraints ("do X before Y").
Edges have weights or costs and you need the cheapest path, not just any path.

Read the full Advanced Graphs guide →

Video walkthroughs

Original problem on LeetCode ↗