Domain 1EasyCORE

Verifying an Alien Dictionary

The problem asks us to determine if a given sequence of words is sorted according to a custom lexicographical order defined by an alien language's alphabet. The inputs are: - `words`: A list of strings representing the words in the alien language. - `order`: A string representing the custom lexicographical order of the alphabet.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

953. Verifying an Alien Dictionary

Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 51.8%


Problem Breakdown

The problem asks us to determine if a given sequence of words is sorted according to a custom lexicographical order defined by an alien language’s alphabet. The inputs are:

  • words: A list of strings representing the words in the alien language.
  • order: A string representing the custom lexicographical order of the alphabet.

The output should be a boolean indicating whether the words are sorted according to the given order.

Implicit constraints and edge cases include:

  • If words is empty or contains only one word, it is trivially sorted.
  • Words can have different lengths. If two words share a common prefix but differ in length (e.g., “app” vs “apple”), the shorter word should come first.
  • The order string contains all 26 lowercase English letters exactly once.

Intuition

A brute-force approach would involve comparing each pair of consecutive words and checking if they are in the correct order according to the custom alphabet. This could be done by simulating a dictionary comparison, but it would be inefficient due to repeated comparisons and lack of direct access to character positions in the custom order.

The key insight is to preprocess the order string to create a mapping from each character to its position in the custom order. This allows for constant-time lookups when comparing characters between words. By using this mapping, we can efficiently determine if two words are in the correct order by comparing their characters one by one until a difference is found.

Approach

  1. Preprocess the Order: Create a dictionary that maps each character in the custom order to its index.
  2. Compare Words: For each pair of consecutive words, compare them character by character using the preprocessed order:
    • If a character in the first word comes after the corresponding character in the second word according to the custom order, return false.
    • If all characters match up to the length of the shorter word and no mismatch is found, ensure that the shorter word does not come after the longer word.
  3. Return Result: If all pairs of words are in the correct order, return true.

Complexity Analysis

  • Time Complexity: O(N * M), where N is the number of words and M is the average length of the words. This is because we potentially compare each pair of consecutive words character by character.
  • Space Complexity: O(1) for the dictionary storing the order mapping, as it has a fixed size of 26 characters.

Solution

def isAlienSorted(words: List[str], order: str) -> bool:
    # Create a mapping from each character to its position in the custom order
    order_index = {char: index for index, char in enumerate(order)}
    
    # Compare each pair of consecutive words
    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        
        # Find the first differing character between the two words
        for k in range(min(len(word1), len(word2))):
            if word1[k] != word2[k]:
                # If they differ, check their order according to the custom alphabet
                if order_index[word1[k]] > order_index[word2[k]]:
                    return False
                break
        else:
            # If no differing character is found, ensure word1 is not longer than word2
            if len(word1) > len(word2):
                return False
    
    return True

Edge Cases Handled

  • Empty Input: The function handles an empty list of words by returning true since there are no words to compare.
  • Single Word: If the list contains only one word, it is trivially sorted, so the function returns true.
  • Words with Different Lengths: The function correctly handles cases where words share a common prefix but differ in length. It ensures that the shorter word comes first if all characters match up to its length.
  • Custom Order: The function uses the provided custom order to determine the correct lexicographical sequence, ensuring that the solution is adaptable to any permutation of the alphabet.

The solution appears to be correct and efficient, with a clear explanation of the approach and complexity analysis.