DIY: Alien Dictionary

Solve the interview question "Alien Dictionary" in this lesson.

We'll cover the following

Problem statement

In this coding exercise, you are given a list of words written in an alien language, where the strings in the words are sorted lexicographically by the rules of this language. Surprisingly, the aliens also use English lowercase letters, but possibly in a different order.

Given a vector of words written in the alien language, you have to return a string of unique letters sorted in lexicographically increasing order in the alien language.

If there are multiple solutions, you can return any one of them. If there is no solution, you can return an empty string: "".

Constraints

You can assume the following constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• All characters in words[i] are English lowercase letters.

Input

The input will contain a vector of strings words. The following two are example inputs to the function:

// Sample Example - 1
words = ["xro", "xma", "per", "pert", "oxh", "olv"]

// Sample Example - 2
words = ["mdx", "mars", "avgd", "dkae"]


Output

// Sample Example - 1
"artevxhmplo"

// Sample Example - 2
""


Coding exercise

For this coding exercise, you have to implement the alienOrder(words) function, where words represents a vector of words from an alien language dictionary. The function will return a string of unique letters sorted in lexicographically increasing order in that alien language.