Alien Dictionary: given sorted words in an alien language, how do you derive the character order?

Q: Alien Dictionary: given sorted words in an alien language, how do you derive the character order?

**Target Audience:** Beginners preparing for coding interviews — no prior algorithms knowledge assumed **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First Archaeologists dig up a dictionary from an alien civilisation. It uses our letters, but in a different alphabetical order, and nobody knows what that order is. The words, however, are clearly **sorted** — it is a dictionary, after all. Can you work out the alien alphabet just from the order of the words? You can, and the trick is the same one you use when you check whether "apple" comes before "apply" in English: you walk both words letter by letter until they first differ. "appl**e**" vs "appl**y**"

The problem

Question presented to candidate: "You are given a list of words from an alien language, and the list is sorted in that language's alphabetical order. The letters are ordinary lowercase letters, but their order is unknown. Return a string with one possible ordering of the letters, or an empty string if no ordering is consistent with the list. Please write it in Python."

What a strong answer should cover:

Only adjacent words are compared, and only their first differing letters give a rule (an edge a -> b); letters after that carry no information.
The prefix trap: a longer word directly before its own prefix makes the input invalid.
A topological sort (Kahn) over the letters that appear, adding each edge once; a cycle means contradictory rules and the answer is "".
Complexity O(C + U^2) with C total characters and U at most 26 letters, and how to tell whether the order is unique.
Python specifics: zip(words, words[1:]) for adjacent pairs, for ... else to detect "no difference found", ord(ch) - 97 indexing, collections.deque, and "".join to build the answer.

Clarifying questions expected:

"Is any valid ordering acceptable, or do you want a specific one?"
"What should I return if the list is contradictory or a word comes before its own prefix?"
"Are all characters lowercase a to z?"

Code / implementation expected: Yes — alienOrder(words) in Python: build edges from adjacent pairs, then Kahn's algorithm.

topological sort
graph
Google

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no prior algorithms knowledge assumed Difficulty: Hard Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

Archaeologists dig up a dictionary from an alien civilisation. It uses our letters, but in a different alphabetical order, and nobody knows what that order is. The words, however, are clearly sorted — it is a dictionary, after all. Can you work out the alien alphabet just from the order of the words?

You can, and the trick is the same one you use when you check whether "apple" comes before "apply"

The solution is hidden so you can try first

11 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonDerive the alien alphabet: normal, contradictory and prefix cases

Practice

PythonIs the order unique, and does it really sort the words? (LeetCode 953 check)