💬 Discord
Sign In
NeetCode #557LC-953EasyGraphsNC 250
← Back to All Problems

#557 · #953 · Verifying an Alien Dictionary(验证外星语词典)

📌 Problem Statement & Constraints

In an alien language the alphabet has a different order given by order. Given a sequence of words, return true if they are sorted lexicographically in this alien order. Constraints: 1 <= words.length <= 100, 1 <= words[i].length <= 20, order.length == 26, all characters in order are unique.

💡 Core Algorithmic Approaches

  1. Compare adjacent word pairs; each pair must be in the alien order.
  2. For a pair, find the first differing position: the characters there must satisfy order.index(a) < order.index(b).
  3. Special case: if one word is a prefix of the other, the shorter must come first -- a longer word appearing before its prefix is a violation (e.g. ["apple", "app"]).
  4. A rank array makes the comparison O(1) per character.

💻 Benchmark Python3 Implementation

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        rank = {ch: i for i, ch in enumerate(order)}   # O(1) character comparison
        for a, b in zip(words, words[1:]):
            for ca, cb in zip(a, b):
                if ca != cb:
                    if rank[ca] > rank[cb]:
                        return False       # out of order at this position
                    break
            else:
                # no differing character: the shorter must come first
                if len(a) > len(b):
                    return False
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(total characters): each character is compared at most once across adjacent pairs.
💾 Space Complexity
O(1) for the rank array (26 entries).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the prefix case: ["apple", "app"] has no differing character in the overlap, so the length check is required.
  • Using order.index(ch) in the loop: O(26) per comparison; the rank array makes it O(1).
  • Comparing the whole strings: only the first differing position matters.
  • Using Python's built-in string comparison: it uses the standard alphabet, not the alien order.