‹ DS&A interview · Socratic
DSA · Graph · #35

Alien Dictionary

Module 43 · difficulty 4/5·30:00starts on first keystroke

There is a new alien language that uses the English lowercase letters, but the **order** among the letters is unknown to you. You are given `words`, a list of strings from the alien language's dictionary. The strings in `words` are sorted **lexicographically** by the rules of this new language. Return a string of the unique letters in the new alien language sorted in **lexicographically increasing order** by the new language's rules. If there is no valid ordering, return `""`. If there are multiple valid orderings, return **any** of them. Implement `function alienOrder(words)`. Note: a string `s` is lexicographically smaller than a string `t` if at the first letter where they differ, the letter in `s` comes before the corresponding letter in `t`. If the first `min(s.length, t.length)` letters are the same, then `s` is smaller iff `s.length < t.length`.

Examples
  • words = ["wrt","wrf","er","ett","rftt"] "wertf"Comparing adjacent words yields w<e, t<f, r<t, e<r, giving order w,e,r,t,f.
  • words = ["z","x"] "zx"z comes before x.
  • words = ["z","x","z"] ""z<x and x<z is contradictory, so no valid ordering exists.
Constraints
  • · 1 <= words.length <= 100
  • · 1 <= words[i].length <= 100
  • · words[i] consists of only lowercase English letters.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.