#0295

Alien Dictionary Order

HardDSA40 min25 XP

Problem

Given words sorted according to an unknown alphabet, return one valid character ordering. Return an empty string if the ordering is impossible.

Why This Matters

Alien Dictionary is a topological-sort problem hidden inside string comparison.

Function Signature

def alien_order(words):

Examples

Example 1

Inputwords = ["wrt","wrf","er","ett","rftt"]

Output"wertf"

Comparing neighboring words gives w before e, e before r, r before t, and t before f.

Constraints

Return the exact requested value.
Handle edge cases cleanly.
Use the intended DSA pattern when brute force would scale poorly.

CodePython

def alien_order(words):
    """
    Input example: words = ["wrt","wrf","er","ett","rftt"]
    Return: "wertf"
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return ""

def alien_order(words):
    """
    Input example: words = ["wrt","wrf","er","ett","rftt"]
    Return: "wertf"
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return ""

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Valid ordering

Input["wrt","wrf","er","ett","rftt"]

Expected"wertf"

The constraints form a chain.

Invalid prefix

Input["abc","ab"]

Expected""

A longer word cannot appear before its exact prefix in sorted order.

Hidden Test Categories

cycle in character graphisolated charactersmultiple valid orders