📘

Alien Dictionary

Given a sorted list of words in an alien language, derive the character ordering. Output the characters in order. If invalid (cycle), output empty string. If multiple valid orderings, output any one.

Example:

Input:

wrt,wrf,er,ett,rftt

Output:

wertf

Reasoning:

The input list of words is compared pairwise to derive the character ordering, starting with wrt and wrf, which implies t comes after f.
Comparing wrt and er implies w comes before e, and er and ett implies r comes before t.
The relationships derived from these comparisons are combined to form a graph, where each character is a node and the edges represent the ordering.
A topological sort is performed on this graph, resulting in the ordering w-e-r-t-f, which is output as the string wertf.

Constraints:

1 <= len(words) <= 100
1 <= len(words[i]) <= 100
All characters are lowercase English letters

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.