Solution: Verifying an Alien Dictionary

Explore how to determine if a list of words in an alien language is sorted according to a given custom order. Learn to implement an efficient solution that uses topological sort concepts to compare adjacent words by their characters and verify their lexicographical order. This lesson helps you understand the process of creating a hash map for character ranking and writing code that correctly handles edge cases involving word prefixes and order inconsistencies.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using topological sort

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 a is considered lexicographically smaller than word b if:
At the first position where the two words differ, the character in a comes before the character in b in the given order string.
If one word is a prefix of the other (and all compared characters are the same), then the shorter word is considered smaller.