269. Alien Dictionary

Alien Dictionary (LeetCode 269) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Topological Sort (Kahn's Algorithm) subpattern.

How to solve Alien Dictionary

Alien Dictionary is a Topological Sort problem, part of Graph Traversal Patterns (DFS & BFS). Master topological sorting using Kahn's BFS algorithm. Solve course schedule and build order problems.

Work towards the solution in these steps:

  1. Think about representing the relationships between characters as a directed graph where edges indicate ordering constraints.
  2. Compare adjacent words to find the first differing character and use that to infer the relative order between those characters.
  3. Build a graph with nodes as characters and edges as ordering rules, then perform a topological sort to find a valid character order.

The reference solution runs in O(N * L + K) time and O(K^2) space.

The Alien Dictionary solution and editorial walks through the full approach with reference code.

Problem statement

You are given a list of strings words, where each string represents a word in an alien language. The words are sorted lexicographically according to the rules of this alien language, but the order of the characters is unknown. Your task is to determine a possible order of the characters in the alien language that is consistent with the given word list.

If there is no valid character order that can explain the given sorting, return an empty string. If there are multiple valid orders, return any of them.

Constraints: - 1 <= words.length <= 100 - 1 <= words[i].length <= 100 - All words consist of lowercase English letters.

Return a string representing a possible order of the characters in the alien language, or an empty string if no valid order exists.

Examples

Example 1

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

Output: "wertf"

Explanation: infers the correct order from a typical alien dictionary example.

Example 2

Input: {"words": ["z", "x"]}

Output: "zx"

Explanation: two words, infers 'z' comes before 'x'.

Topics and companies

Topics: Array, String, Depth-First Search, Breadth-First Search, Graph, Topological Sort.

Reported in interviews at Facebook, Amazon, Airbnb, Pinterest, Google, Microsoft, ByteDance.

How to practise Alien Dictionary on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N * L + K) time and O(K^2) space.

Open Alien Dictionary in the code editor, or read the Alien Dictionary editorial for a worked solution with its approach and complexity analysis.

Where Alien Dictionary sits in the DSA pattern sheet

Problems related to Alien Dictionary

Other problems that use the same Graph BFS - Topological Sort (Kahn's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

Alien Dictionary FAQ

What is the LeetCode number of Alien Dictionary?

Alien Dictionary is LeetCode problem 269, rated Hard.

What pattern is used to solve Alien Dictionary?

Alien Dictionary is a Topological Sort problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Topological Sort (Kahn's Algorithm) subpattern.

What is the time complexity of Alien Dictionary?

The reference solution runs in O(N * L + K) time and O(K^2) space.

Which companies ask Alien Dictionary?

Alien Dictionary has been reported in interviews at Facebook, Amazon, Airbnb, Pinterest, Google, Microsoft, ByteDance.

Preparing this workspace.