You are given a list of words words sorted lexicographically by the rules of an unknown alien language. Return a string representing a valid ordering of the language's characters.

• If there are multiple valid orders, return any of them.
• If no valid ordering exists, return an empty string "".
• The result should include every distinct character that appears in words.

Example 1:

Input: [\"wrt\",\"wrf\",\"er\",\"ett\",\"rftt\"]
Output: \"wertf\"
Explanation: From the first differing letters among adjacent words: w<e, r<t, e<r, t<f.

 

Example 2:

Input: [\"z\",\"x\",\"z\"]
Output: \"\"
Explanation: The constraints imply a cycle z<x and x<z.

 

Example 3:

Input: [\"abc\",\"ab\"]
Output: \"\"
Explanation: Invalid because a longer word appears before its prefix.

Constraints:

• 1 \le words.length \le 100
• 1 \le words[i].length \le 100
• words[i] consists of lowercase English letters.

You are given a list of words words sorted lexicographically by the rules of an unknown alien language. Return a string representing a valid ordering of the language's characters.

• If there are multiple valid orders, return any of them.
• If no valid ordering exists, return an empty string "".
• The result should include every distinct character that appears in words.

Example 1:

Input: [\"wrt\",\"wrf\",\"er\",\"ett\",\"rftt\"]
Output: \"wertf\"
Explanation: From the first differing letters among adjacent words: w<e, r<t, e<r, t<f.

 

Example 2:

Input: [\"z\",\"x\",\"z\"]
Output: \"\"
Explanation: The constraints imply a cycle z<x and x<z.

 

Example 3:

Input: [\"abc\",\"ab\"]
Output: \"\"
Explanation: Invalid because a longer word appears before its prefix.

Constraints:

• 1 \le words.length \le 100
• 1 \le words[i].length \le 100
• words[i] consists of lowercase English letters.