Verifying an Alien Dictionary
Explore how to verify whether a list of words follows an alien dictionary order by using topological sorting concepts. Learn to compare words based on a custom alphabet sequence and implement a solution that checks lexicographic ordering in an alien language.
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 = [“wrt”, “wrf”, “er”, “ett”, “rftt”]
order = “hlabcdgiwjkmnopqerstfuvxyz”
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:
bool VerifyAlienDictionary(vector<string>& words, string order){// Replace this placeholder return statement with your codereturn false;}