Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you.

You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language.

Derive the order of letters in this language.

Note:

  1. You may assume all letters are in lowercase.
  2. Every letter that appears in the input must also appear in the output, and your output cannot have characters not in the input.
  3. If no ordering of letters makes the dictionary sorted lexicographically, return an empty string.
  4. There may be multiple valid orders. If that's the case, return the smallest in normal lexicographical order.

Input

  • words: A list of strings of size n, representing the dictionary words sorted lexicographically in the alien language.

Output

A string representing the smallest possible lexicographical order, or an empty string if no valid order exists.

Examples

Example 1:

Input:

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

Output: zx

Explanation:

Example 2:

Input:

words = ["z","x"]

Output: zx

Explanation:

From z and x,we can get z < x. So return zx.

Constraints

  • 2 <= n <= 10000
  • 1 <= words[i] <= 30

Try it yourself

Solution

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade