Alien Dictionary

Problem

Given words sorted by an alien alphabet, return a string of the unique letters in a valid order, or the empty string if no valid order exists.

Derive precedence edges from the first differing character of each adjacent pair, and reject a longer word that appears before its own prefix. Use Kahn's algorithm with a min-heap for the lexicographically smallest order.

Hint

A word appearing before its own prefix makes the ordering impossible, and leftover letters mean a cycle.

Test cases

case 1

in: [["wrt","wrf","er","ett","rftt"]]

expected: "wertf"

case 2

in: [["z","x"]]

expected: "zx"

case 3

in: [["z","x","z"]]

expected: ""

case 4

in: [["abc","ab"]]

expected: ""

case 5

in: [["a"]]

expected: "a"

case 6

in: [["ab","adc"]]

expected: "abcd"

Starter codePython

def alien_order(words):
    # Your code here
    pass

6 test cases · run your code against them in the editor