PIXELBANKv8.2.1
Menu
Sign In

Alien Dictionary

HardGraphs

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

Test Results

0/0
Run code to see test results.