Solution: Verifying an Alien Dictionary

Explore the process of verifying whether a list of words follows the lexicographical order of an alien dictionary. This lesson helps you understand an optimized approach using topological sort to efficiently compare adjacent words based on a custom alphabet order. You will learn to implement a solution that checks word order correctly, considering prefixes and character positions, while analyzing time and space complexity for the algorithm.

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.