Problem Description
In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.
Key Insights
- The alien language has a different lexicographical order defined by a string.
- We need to compare each word with the next one to ensure they are in the correct order.
- If two words are identical up to the length of the shorter one, the shorter word should come first.
- A mapping from characters to their indices in the alien order helps simplify comparisons.
Space and Time Complexity
Time Complexity: O(N * M), where N is the number of words and M is the maximum length of a word.
Space Complexity: O(1), since the order string is a fixed size (26 characters).
Solution
To solve the problem, we will use a hash map to store the index of each character according to the alien order. This allows us to quickly compare the characters of the words based on their indices in the alien language. We will iterate through the list of words, comparing each pair of consecutive words using their character indices. If we find any instance where the words are out of order, we will return false. If we finish checking all pairs without finding any issues, we will return true.