Problem Description

You're given words from an alien language that uses the same 26 lowercase English letters (a-z), but in a potentially different alphabetical order. The aliens have their own custom ordering of these letters.

Your task is to determine whether a given list of words is sorted according to the alien dictionary order.

Input:

• words: A list of strings containing words written in the alien language
• order: A string of 26 characters representing the alien alphabetical order (a permutation of a-z)

Output:

• Return true if the words are sorted lexicographically according to the alien order
• Return false otherwise

Example: If the alien order is "hlabcdefgijkmnopqrstuvwxyz" (where h comes before l, which comes before a, etc.), then:

• ["hello", "leetcode"] would be sorted correctly because h comes before l in the alien order
• ["word", "world"] would need to be checked character by character using the alien order

The solution creates a mapping of each character to its position in the alien alphabet, then compares words character by character up to position 20 (assuming maximum word length). For each position i, it checks if all words maintain the correct order at that character position. If at any position the ordering is violated (a previous character has a higher order value than the current one), it returns false. If all characters at a position are different and properly ordered, the words are confirmed to be sorted.

Intuition

To check if words are sorted in an alien dictionary, we need to compare them the same way we'd compare words in a regular dictionary - character by character from left to right. The key insight is that we need to translate the alien ordering into something we can work with numerically.

Think about how you check if words are sorted in English: you compare the first letters, and if they're the same, you move to the second letters, and so on. The difference here is that instead of using the standard a < b < c... ordering, we have a custom ordering defined by the order string.

The natural approach is to create a mapping where each character gets assigned its position in the alien alphabet. For example, if order = "bac...", then b has position 0, a has position 1, and c has position 2. This way, we can compare characters numerically - a character with a smaller position value comes before one with a larger position value.

The solution iterates through each character position (column-wise) across all words. At position i, it extracts the i-th character from each word and checks if these characters are in non-decreasing order according to the alien alphabet. If we find any position where a word has a character that comes after the corresponding character in the previous word (higher position value), the list isn't sorted.

The clever part is handling words of different lengths - when a word doesn't have a character at position i (it's too short), we treat it as having value -1, which naturally comes before any actual character. This handles cases like "app" coming before "apple" correctly.

The algorithm stops early when it finds a position where all words have different characters that are properly ordered (the valid flag), confirming the sort order without needing to check further positions.

Solution Approach

The solution implements a column-wise comparison strategy to verify the alien dictionary ordering:

Step 1: Create Character-to-Position Mapping

m = {c: i for i, c in enumerate(order)}

This creates a dictionary where each character maps to its position in the alien alphabet. For example, if order = "bac...", then m = {'b': 0, 'a': 1, 'c': 2, ...}.

Step 2: Column-wise Iteration The algorithm iterates through character positions 0 to 19 (assuming maximum word length of 20):

for i in range(20):

Step 3: Character Comparison at Each Position For each position i, the algorithm:

• Initializes prev = -1 to track the previous word's character value
• Sets valid = True to check if all characters at this position are distinct and ordered

Step 4: Process Each Word

for x in words:
    curr = -1 if i >= len(x) else m[x[i]]

For each word, it extracts the character at position i:

• If the word is too short (i >= len(x)), assign -1 as the value
• Otherwise, get the character's position value from the mapping m[x[i]]

Step 5: Order Validation

if prev > curr:
    return False
if prev == curr:
    valid = False
prev = curr

• If prev > curr: The previous word's character comes after the current word's character in the alien order, so the list is not sorted - return False
• If prev == curr: The characters are the same, so we need to check the next position - set valid = False
• Update prev for the next iteration

Step 6: Early Termination

if valid:
    return True

If valid remains True after checking all words at position i, it means all characters at this position are different and in the correct order. The words are confirmed to be sorted, so return True.

Step 7: Default Return If the loop completes without finding a definitive answer (all positions checked with ties), return True as the words are considered sorted.

This approach efficiently handles edge cases like words of different lengths and ensures lexicographic ordering according to the alien alphabet.

Example Walkthrough

Let's walk through the algorithm with a concrete example:

Input:

• words = ["cat", "car", "card"]
• order = "cabdefghijklmnopqrstuvwxyz" (where 'c' comes first, then 'a', then 'b', etc.)

Step 1: Create mapping

m = {'c': 0, 'a': 1, 'b': 2, 'd': 3, ..., 't': 19, 'r': 17, ...}

Step 2: Check position i = 0 (first character)

• Word "cat": character 'c' → m['c'] = 0
• Word "car": character 'c' → m['c'] = 0
• Word "card": character 'c' → m['c'] = 0

Comparison sequence:

• prev = -1 (initial)
• "cat": curr = 0, prev (-1) ≤ curr (0) ✓, prev = curr so valid = False
• "car": curr = 0, prev (0) ≤ curr (0) ✓, prev = curr so valid = False
• "card": curr = 0, prev (0) ≤ curr (0) ✓, prev = curr so valid = False

All first characters are the same, so valid = False, continue to next position.

Step 3: Check position i = 1 (second character)

• Word "cat": character 'a' → m['a'] = 1
• Word "car": character 'a' → m['a'] = 1
• Word "card": character 'a' → m['a'] = 1

Comparison sequence:

• prev = -1 (reset)
• "cat": curr = 1, prev (-1) ≤ curr (1) ✓, prev = curr so valid = False
• "car": curr = 1, prev (1) ≤ curr (1) ✓, prev = curr so valid = False
• "card": curr = 1, prev (1) ≤ curr (1) ✓, prev = curr so valid = False

All second characters are the same, continue to next position.

Step 4: Check position i = 2 (third character)

• Word "cat": character 't' → m['t'] = 19
• Word "car": character 'r' → m['r'] = 17
• Word "card": character 'r' → m['r'] = 17

Comparison sequence:

• prev = -1 (reset)
• "cat": curr = 19, prev (-1) ≤ curr (19) ✓, update prev = 19
• "car": curr = 17, prev (19) > curr (17) ✗

Since 19 > 17, the character 't' comes after 'r' in the alien order, but "cat" appears before "car" in our list. This violates the sorting order.

Result: Return False

The words are not sorted according to the alien dictionary because "cat" should come after "car" (since 't' comes after 'r' in the alien alphabet).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * m) where n is the total number of characters across all words and m is the length of the alphabet (order string).

• Creating the mapping dictionary m takes O(m) time where m is the length of the order string (26 for the alphabet).
• The outer loop runs at most 20 times (constant).
• The inner loop iterates through all words, which is O(w) where w is the number of words.
• For each word, we access at most one character and perform a dictionary lookup, which is O(1).
• In the worst case, we examine all characters across all words before returning, giving us O(n) where n is the total number of characters.
• Since the outer loop is bounded by a constant (20), the overall time complexity is O(n + m), which simplifies to O(n) when n >> m.

However, a more precise analysis shows that we iterate through positions (up to 20) and for each position check all words, so it's O(min(20, maxLength) * w) where w is the number of words and maxLength is the length of the longest word. This can be simplified to O(n) where n is the total number of characters across all words.

Space Complexity: O(m) where m is the length of the order string.

• The mapping dictionary m stores each character in the order string with its index, requiring O(m) space.
• The variables prev, curr, and valid use constant space O(1).
• No additional data structures are created that scale with input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Words with Different Lengths

A critical pitfall in this solution is the assumption that shorter words should always come before longer words when one is a prefix of the other. The code assigns -1 to positions beyond a word's length, which makes shorter words automatically "smaller" than longer words at those positions.

Problem Example:

• Alien order: "abcdefghijklmnopqrstuvwxyz" (standard order)
• Words: ["apple", "app"]
• Expected: False (because "apple" should come after "app" in standard lexicographic order)
• Current code returns: True (incorrectly)

Why it fails: When comparing at position 3:

• "apple" has character 'l' with value 11
• "app" has no character (assigned -1)
• Since 11 > -1, the code thinks "apple" > "app", which seems correct
• But the issue is that the code continues checking and never properly validates that "app" should come first

2. Fixed Position Limit of 20

The hardcoded limit of 20 positions assumes no word will be longer than 20 characters. If words exceed this length and differ only after position 20, the algorithm will incorrectly return True.

Solution:

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        # Create character-to-position mapping
        char_to_position = {char: position for position, char in enumerate(order)}
      
        # Compare adjacent words pairwise
        for i in range(len(words) - 1):
            word1, word2 = words[i], words[i + 1]
          
            # Compare characters one by one
            for j in range(len(word1)):
                # If word2 is shorter than word1 and is a prefix, wrong order
                if j >= len(word2):
                    return False
              
                # Get character values in alien order
                char1_value = char_to_position[word1[j]]
                char2_value = char_to_position[word2[j]]
              
                # If char1 comes after char2 in alien order, wrong order
                if char1_value > char2_value:
                    return False
                # If char1 comes before char2, this pair is valid
                elif char1_value < char2_value:
                    break
                # If equal, continue to next character
          
        return True

Key Improvements:

1. Pairwise comparison: Instead of column-wise checking, compare adjacent words directly
2. Proper prefix handling: Explicitly check if a longer word comes before its prefix
3. No arbitrary length limit: Works for words of any length
4. Clearer logic: Each word pair is validated completely before moving to the next