Verifying an Alien Dictionary
Explore how to determine if a list of words is sorted based on a given alien alphabet order using topological sorting. Understand lexicographical comparison rules and implement a solution that handles prefix cases and character ordering 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 = [“alpha”, “bravo”, “charlie”, “delta”]
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:
import java.util.*;class VerifyDictionary {public static boolean verifyAlienDictionary(String[] words, String order) {// Replace this placeholder return statement with your codereturn false;}}