Alien Dictionary
Alien Dictionary 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.
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.
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), where N is the number of words, L is the average word length, and K is the number of unique characters. Building the graph takes O(N * L), and topological sort takes O(K + E), where E is the number of edges (at most K^2). time and O(K^2), where K is the number of unique characters. This is for the adjacency list and indegree map. 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
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Graph BFS - Topological Sort (Kahn's Algorithm) subpattern
- The full DSA patterns sheet
- All coding practice problems
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:
- Build a Matrix With Conditions — Hard, same subpattern
- Find All Possible Recipes from Given Supplies — Medium, same subpattern
- Largest Color Value in a Directed Graph — Hard, same subpattern
- Minimum Height Trees — Medium, same subpattern
- Parallel Courses — Medium, same subpattern
- Parallel Courses III — Hard, same subpattern