Verifying an Alien Dictionary
Explore how to verify whether a list of words is sorted lexicographically based on a given alien alphabet order. Understand the problem constraints and implement a solution using topological sort concepts to check word order efficiently in coding interviews.
We'll cover the following...
Statement
In an alien language, the alphabet consists of the same lowercase English letters but arranged in a different order.
Given a list of words, words, written in this alien language, and a string order representing the order of the alien alphabet (as a permutation of lowercase letters), return TRUE if the words are sorted lexicographically according to order; otherwise, return FALSE.
Note: A word
ais considered lexicographically smaller than wordbif:
At the first position where the two words differ, the character in
acomes before the character inbin the givenorderstring.If one word is a prefix of the other (and all compared characters are the same), then the shorter word is considered smaller.
Constraints:
-
words.length -
words[i].length order.length- All the characters in
words[i]andorderare lowercase English letters.
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Verifying an Alien Dictionary
What is the output if the following list of words and order are given as input?
words = [“hello”, “to”, “my”, “world”]
order = “hlabcdefgijkmnopqrstuvwxyz”
TRUE
FALSE
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 the following coding playground:
def verify_alien_dictionary(words, order):# Replace this placeholder return statement with your codereturn False