Alien Dictionary Order | Dataford Interview Questions

Snap Chat may receive word lists sorted according to an unknown alien alphabet. Given the sorted list, infer the character ordering that is consistent with the list.

Return the lexicographically smallest valid ordering of all distinct characters. If no ordering exists, return an empty string. An ordering is invalid when adjacent words contradict the inferred precedence rules, when a longer word appears before its exact prefix, or when the precedence graph contains a cycle.

Formal Specification

Implement alien_order(words), where words is a list of lowercase strings. Return a string containing every distinct character exactly once, or "" if the input is invalid. Compare each adjacent pair of words and use only their first differing character to infer an edge.

Constraints

1 <= len(words) <= 10^4
1 <= len(words[i]) <= 10^4
The total number of characters across all words is at most 10^5
Words contain only lowercase English letters
The output contains every distinct character exactly once
Return the lexicographically smallest valid ordering when one exists

Function Signature

def alien_order(words):

Your question is Alien Dictionary Order. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem