Alien Dictionary

Problem

There is a new alien language that uses the English alphabet, but the order of the letters is unknown.

You are given a list of strings words from the alien language’s dictionary. It is claimed that the strings in words are sorted lexicographically by the rules of this new language.

If this claim is incorrect, and the given arrangement of strings in words cannot correspond to any order of letters, return "".

Otherwise, 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 are multiple solutions, return any of them.

A string a is lexicographically smaller than a string b if either of the following is true:

• The first letter where they differ is smaller in a than in b.
• a is a prefix of b and a.length < b.length.

Examples

Example 1:

Input: words = ["z","o"]

Output: "zo"

Explanation:
From "z" and "o", we know 'z' < 'o', so return "zo".

Example 2:

Input: words = ["hrn","hrf","er","enn","rfnn"]

Output: "hernf"

Explanation:

• from "hrn" and "hrf", we know 'n' < 'f'
• from "hrf" and "er", we know 'h' < 'e'
• from "er" and "enn", we know 'r' < 'n'
• from "enn" and "rfnn" we know 'e' < 'r'
• so one possible solution is "hernf"

Constraints

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

You should aim for a solution with O(N + V + E) time and O(V + E) space, where N is the sum of the lengths of all the strings, V is the number of unique characters (vertices), and E is the number of edges.

Solution

x