💬 Discord
Sign In
NeetCode #634LC-269HardAdvanced GraphsBlind 75NC 150NC 250NC Algo100
← Back to All Problems

#634 · #269 · Alien Dictionary(火星词典)

📌 Problem Statement & Constraints

You are given a list of words sorted lexicographically in an alien language. Derive the order of the letters. If the order is invalid, return the empty string. Constraints: 1 <= words.length <= 100, 1 <= words[i].length <= 100, all words consist of lowercase letters.

💡 Core Algorithmic Approaches

  1. Compare adjacent words: the first differing character gives a directed edge between two letters.
  2. Collect all distinct letters as graph nodes, then run a topological sort.
  3. Invalid cases: a longer word appearing before its own prefix (e.g. ["abc", "ab"]), or a cycle in the derived graph.
  4. If the topological order contains all letters, it is a valid answer; otherwise return an empty string.

💻 Benchmark Python3 Implementation

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        from collections import defaultdict, deque
        g = defaultdict(set)               # sets avoid duplicate edges
        indeg = {c: 0 for w in words for c in w}
        for a, b in zip(words, words[1:]):
            # a longer word cannot come before its own prefix
            if len(a) > len(b) and a.startswith(b):
                return ""
            for ca, cb in zip(a, b):
                if ca != cb:
                    if cb not in g[ca]:    # avoid counting a duplicate edge
                        g[ca].add(cb)
                        indeg[cb] += 1
                    break              # only the first difference matters
        q = deque(c for c in indeg if indeg[c] == 0)
        res = []
        while q:
            c = q.popleft()
            res.append(c)
            for nxt in g[c]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    q.append(nxt)
        if len(res) != len(indeg):
            return str()               # a cycle -> invalid order
        return "".join(res)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(total characters): each character pair is examined once.
💾 Space Complexity
O(1) for the graph (at most 26 nodes).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the prefix invalidity check: ["abc", "ab"] is not a valid sorted order.
  • Counting duplicate edges: the in-degree would be inflated, breaking the sort.
  • Using a list instead of a set for adjacency: duplicate edges would be added repeatedly.
  • Ignoring characters after the first difference: only the first difference defines an edge.