Solution: Verifying an Alien Dictionary
Explore how to determine if words written in an alien language are lexicographically sorted by a custom alphabet order. This lesson guides you through both naive and optimized approaches, focusing on the use of topological sort to compare adjacent words efficiently. Understand the implementation details, analyze time and space complexity, and learn how to handle edge cases such as prefix words while verifying dictionary order.
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