Alien Dictionary

if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:

Check for invalid prefix case where longer word precedes its prefix.

This condition violates lexicographical order rules, so detecting it early allows immediate termination with an empty string, preventing incorrect results.

if dfs(c):

If DFS detects a cycle starting from this character, return empty string.

Cycle detection invalidates the ordering, so the algorithm must terminate early with no solution.

return ""

Return empty string upon detecting invalid prefix ordering.

Returning immediately signals no valid character order exists due to contradictory input ordering.

if w1[j] != w2[j]:

Check if characters at current position differ.

Identifying the first differing character pair is critical to establishing a precedence edge in the graph.

adj[w1[j]].add(w2[j])

Add an edge from the character in the first word to the character in the second word.

This edge encodes the ordering constraint that the first character must come before the second in the alien language.

if c in visit:

Return visit state if character has been visited or is currently visiting.

This line prevents redundant work and detects cycles by returning True if a cycle is found (node is currently visiting).

return visit[c]

Mark character as currently visiting (True).

Marking as visiting signals the start of exploration; encountering this state again indicates a cycle.

for nei in adj[c]:

If a cycle is detected in any neighbor, propagate True to indicate failure.

Early termination upon cycle detection prevents unnecessary traversal and signals invalid ordering.

if dfs(nei):

Return True immediately if a cycle is found.

This return propagates cycle detection up the recursion stack, aborting the topological sort.

res.append(c)

Append character to result list after visiting all neighbors.

Appending post-recursion ensures characters appear after all their dependencies, building a valid topological order in reverse.

return ""

Return empty string upon cycle detection.

Signals to the caller that no valid alien dictionary ordering exists due to contradictory constraints.

return "".join(res[::-1])

Return the reversed result list as a string representing the alien dictionary order.

Reversing the postorder traversal list produces the correct topological order of characters consistent with all precedence constraints.

adj = { c: set() for w in words for c in w }

Initialize adjacency list mapping each character to an empty set of neighbors.

Creating an adjacency set for every character ensures all characters appear as nodes in the graph, even if they have no outgoing edges, which is essential for a complete topological sort.

for j in range(min_len):

Iterate through characters up to the minimum length to find first differing character.

The first differing character between adjacent words determines a direct precedence edge; subsequent characters do not provide valid ordering information.

visit = {}

Initialize a dictionary to track visit state of characters during DFS.

Tracking visit state is essential for cycle detection and preventing redundant traversals during topological sort.

def dfs(c):

Define DFS function to traverse graph and detect cycles.

DFS enables depth-first exploration of dependencies, allowing cycle detection and ordering construction in one pass.

visit[c] = True

Recursively visit all neighbors of the current character.

Exploring neighbors enforces all precedence constraints and detects cycles in downstream nodes.

visit[c] = False

Mark character as fully visited (False).

Marking as visited indicates the node and its descendants have been processed without cycles, allowing reuse of this state.

for i in range(len(words) - 1):

Iterate through pairs of adjacent words to infer ordering constraints.

Comparing adjacent words is the only way to extract direct precedence relations between characters, as the input words are sorted lexicographically according to the alien language.

break

Break out of the loop after adding the first precedence edge.

Only the first differing character pair matters for ordering; further characters do not affect the relative order of these two words.

res = []

Initialize a list to accumulate the topological order of characters.

Characters are appended post-recursion to build the order in reverse; this list will be reversed before returning the final result.

for c in adj:

Iterate over all characters in the graph to initiate DFS.

Ensures all disconnected components and isolated nodes are processed for a complete ordering.

min_len = min(len(w1), len(w2))

Determine the minimum length of the two words for safe comparison.

Comparisons beyond the shorter word's length are invalid and can cause index errors; this also helps detect invalid prefix cases.

return True

End of neighbor iteration.

Completing neighbor exploration without cycle detection means current node is safe to finalize.

w1, w2 = words[i], words[i + 1]

Assign the current and next words for comparison.

Storing the two words simplifies subsequent character-by-character comparison and prefix checks.