Alien Dictionary

The key idea

A sorted dictionary only tells you about the FIRST position where two adjacent words differ: that earlier character must come before the later one. Collect those single rules as directed edges, then a topological sort of the letters gives the alien order. A cycle means no order exists.

Problem

There is a new alien language that uses the lowercase English alphabet, but the order of the letters is unknown to you. You are given a list of strings words from this language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new language, sorted in the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

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 letter in t in the alien order. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of only lowercase English letters

Examples

Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"

Input: words = ["z","x"] Output: "zx"

Input: words = ["z","x","z"] Output: ""

Complexity

Time: O(C) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →