Verifying an Alien Dictionary

Try to solve the Verifying an Alien Dictionary problem.

We'll cover the following

Statement#

You’re given a list of words with lowercase English letters in a different order, written in an alien language. The order of the alphabet is some permutation of lowercase letters of the English language.

We have to return TRUE if the given list of words is sorted lexicographically in this alien language.

Constraints:

  • 1≤1 \leq words.length ≤103\leq 10^3
  • 1≤1 \leq words[i].length ≤20\leq 20
  • order.length ==26== 26
  • All the characters in words[i] and order are lowercase English letters.

Examples#

Created with Fabric.js 3.6.6 True Input Output Sample example 1 words "coding" "interview" order "abcdiefghjklmnorpqstuvwxyz" As "c" precedes "i" in the order, the words are lexicographically sorted.

1 of 4

Created with Fabric.js 3.6.6 Input False Output Sample example 2 words "educated" "educate" order "educatbfghijklmnopqrsvwxyz" Conversely, the first seven letters "educate" match,and the second word is shorter in size. According tolexicographical rules, "educated" > "educate", because "d" > "Θ", where "Θ" is defined as the blank character,which is less than any other character.

2 of 4

Created with Fabric.js 3.6.6 True Input Output Sample example 3 order "hwabcdefgijklmnopqrstuvxyz" words "hello" "word" "world" As "h" precedes "w" and "d" precedes "l", in the order, the words are lexographically sorted.

3 of 4

Created with Fabric.js 3.6.6 False Output Input Sample example 4 words "passengers" "to" "the" "unknown" order "ptuhabcdefgijklmnoqrsvwxyz" As "h" precedes "o" in the order, the words are not lexicographically sorted.

4 of 4

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

1

What is the output if the following list of words and order are given as input?

words = [“wrt”, “wrf”, “er”, “ett”, “rftt”]

order = “hlabcdgiwjkmnopqerstfuvxyz”

A)

TRUE

B)

FALSE

Question 1 of 40 attempted

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.

Drag and drop the cards to rearrange them in the correct sequence.

Store the ranking of each letter from the order string in the data structure.

Iterate over the two adjacent words in the words list.

If words[i + 1] ends before words[i], return FALSE.

Else, if the characters in both of the words are different and words are in correct order, exit and move to the next two adjacent words.

Else, return FALSE if the characters are different in both words and words are not in correct order.

At the end of the loop, all of the adjacent words have been examined, which ensures that all of the words are sorted. Therefore, return TRUE.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
Input #2
%0 node_01 h
Visualization for Input #1
Verifying an Alien Dictionary

Topological Sort: Introduction

Solution: Verifying an Alien Dictionary