Alien Dictionary
Explore how to use topological sort to find the lexicographical order of characters in an alien language from a list of words. Understand the problem constraints and implement code to handle unique ordering scenarios or detect invalid orders.
We'll cover the following...
Statement
You are given a list of words written in an alien language, where the words are sorted lexicographically by the rules of this language. Surprisingly, the aliens also use English lowercase letters, but possibly in a different order.
Given a list of words written in the alien language, return a string of unique letters sorted in the lexicographical order of the alien language as derived from the list of words.
If there’s no solution, that is, no valid lexicographical ordering, you can return an empty string "".
If multiple valid orderings exist, you may return any of them.
Note: A string,
a, is considered lexicographically smaller than stringbif:
At the first position where they differ, the character in
acomes before the character inbin the alien alphabet.If one string is a prefix of the other, the shorter string is considered smaller.
Constraints:
-
words.length -
words[i].length - All characters in
words[i]are English lowercase letters.
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:
Alien Dictionary
What is the output if the following list of words is given as input?
Select all that apply.
[“wrt”, “wrf”, “er”, “ett”, “rftt”] Multi-select
“wrfet”
“wreft”
“wertf”
“wfert”
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in main.py in the following coding playground. We have provided some useful code templates in the other file that you may build on to solve this problem.
from collections import defaultdict, Counter, dequedef alien_order(words):# Replace this placeholder return statement with your codereturn ""