1042. Alien Dictionary — Find Letter Order

Given a list of words sorted lexicographically by the rules of an unknown alien language, derive the order of its letters. Return the letters in a valid order as a string (lexicographically smallest among valid orders); return an empty string if no valid order exists (a contradiction or an invalid prefix like a longer word before its prefix). The input is JSON {words}.

Input: JSON {words}.

Output: String — a valid letter order, or empty.

Examples

Input: {"words":["wrt","wrf","er","ett","rftt"]}
Output: wertf
Explanation: Derived letter order.

Input: {"words":["abc","ab"]}
Output: 
Explanation: Invalid: prefix after longer word.

Input: {"words":["z","x"]}
Output: zx
Explanation: z precedes x.

Constraints

• 1<=words<=1000
• lowercase letters

Asked by