We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Verifying an Alien Dictionary

Number: 990

Difficulty: Easy

Paid? No

Companies: Meta, Amazon, Google, Apple, TikTok, Uber, Microsoft, Wix

Problem Description

Given a list of words and a custom order of the English lowercase letters (which represents the alien language ordering), determine if the words are sorted lexicographically according to this alien dictionary order.

Key Insights

  • Create a mapping from each character to its rank based on the provided alien order.
  • Compare every adjacent pair of words to ensure the first one is not greater than the next.
  • In comparing two words, iterate over characters and decide order based on the mapping.
  • Handle the prefix case: if two words match up to the length of the shorter word, the shorter must come first.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of words and m is the average length of the words. Space Complexity: O(1) aside from the input space, since the mapping is fixed at 26 characters.

Solution

The solution uses a hash map (or dictionary) to convert each character in the alien order into its corresponding index. This allows for constant time lookups when comparing characters between words. We then iterate pairwise through the list of words and for each pair, compare the characters until a difference is found. If the current character from the first word ranks higher than that from the second word, or if one word is a prefix of the other (and the longer comes first), then the list is not sorted. If no invalid order is encountered, return true.

Code Solutions

# Build a dictionary mapping for the alien alphabet order
def isAlienSorted(words, order):
    # Create a mapping from character to its index in the alien dictionary
    order_index = {char: i for i, char in enumerate(order)}
    
    # Function to compare two words using the alien dictionary order
    def compare(word1, word2):
        # Loop through each character in both words
        for c1, c2 in zip(word1, word2):
            # If the characters differ, decide the order based on alien mapping
            if order_index[c1] != order_index[c2]:
                return order_index[c1] - order_index[c2]
        # If all characters are the same for the shorter length, the shorter word should come first
        return len(word1) - len(word2)
    
    # Compare each adjacent pair of words
    for i in range(len(words) - 1):
        if compare(words[i], words[i+1]) > 0:
            return False
    return True

# Example usage:
# print(isAlienSorted(["hello", "leetcode"], "hlabcdefgijkmnopqrstuvwxyz"))
← Back to All Questions