Verify an Alien Dictionary

Statement

Given a vector of words written in an alien language and the order of their alphabet, return true only if the given words are sorted in ascending lexicographical order in the alien language.

Given the standard English language ordering of letters, “cap” is lexicographically smaller than “cat”, because “p” appears before “t” in the alphabet. Similarly, “aleph” is lexicographically smaller than “alpha.”

Examples

The input contains a vector of strings words, which contains the words to verify, and a string of characters, order, that defines the lexicographic order of the letters in the alien language.

The following are example inputs to the function, along with the expected outputs:

Example 1

Sample input

words = ["hello", "world"]
order = "hwabcdefgijklmnopqrstuvxyz"

Expected output

For the above input, as “h” appears before “w” in the alien alphabet, the output is:

true

Example 2

Sample input

words = ["educated", "educate"]
order = "educatebfghijklmnopqrsvwxyz"

Expected output

For the above input, the second word is a prefix of the first word and should be listed before it. Therefore, the output will be:

false

Constraints

We can assume the following constraints:

  • The maximum length of the dictionary is 100 words.
  • The maximum length of a word is 20 characters.
  • Length of the alien alphabet is 26 characters.
  • All characters in words[i] and order are English lowercase letters.

Try it yourself

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.