Verifying an Alien Dictionary
Understand how to determine if words are sorted lexicographically in an alien language by comparing characters based on a given order. Explore the use of topological sort to solve this common pattern problem, enhancing your ability to analyze problem statements and implement efficient solutions 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 array of words and order are given as input?
words = [“you”, “are”, “a”, “great”, “human”]
order = “abcdefghijklmnopqrstuvwxyz”
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:
package mainfunc verifyAlienDictionary(words []string, order string) bool {// Replace this placeholder return statement with your codereturn false}