A new alien language uses lowercase Latin letters, but the order of the letters is not known.
You are given a list of non-empty dictionary words. The words are already sorted in lexicographical order according to the rules of this alien language.
Your task is to derive the lexicographically smallest valid ordering of letters in the alien language.
If the given dictionary order is impossible or contradictory, return an empty string.
Method Signature
String alienOrder(List<String> words)
Parameters
words: A list of non-empty lowercase strings sorted according to the alien language dictionary order.- You must never use
null as a parameter value.
Returns
- Return a string representing the lexicographically smallest valid ordering of letters in the alien language.
- When choosing among multiple valid alien letter orderings, compare returned strings using normal lowercase English lexicographical order, where
'a' < 'b' < ... < 'z'.
- If the dictionary order is invalid, return an empty string
"".
Rules
- All words contain only lowercase Latin letters from
'a' to 'z'.
- The input list
words is intended to be sorted according to the alien language order.
- To compare two adjacent words, look at the first position where the two words have different letters.
- If the first different letters are
x and y, then x must appear before y in the alien letter order.
- If one word is a prefix of another word, then the shorter word must appear before the longer word.
- For example,
"abc" appearing before "abcd" is valid.
- For example,
"abcd" appearing before "abc" is invalid.
- If the derived letter ordering contains a cycle or contradiction, return
"".
- Every unique letter that appears in
words must appear exactly once in the returned order when the order is valid.
Constraints
1 ≤ words.size() ≤ 10001 ≤ words[i].length() ≤ 100words[i] contains only lowercase English letters.words[i] is never empty.words is never null.- No value inside
words is null.
- You must never use
null as a parameter value.
- The total number of unique letters is at most
26.
Examples
Example 1
Input: alienOrder(words = ["baa","abcd","abca","cab","cad"])
Output: "bdac"
Explanation: Comparing adjacent words gives ordering rules b before a, d before a, a before c, and b before d. These rules force b before d before a before c. Therefore, the lexicographically smallest valid order using these letters is "bdac".
Example 2
Input: alienOrder(words = ["abc","abx"])
Output: "abcx"
Explanation: The first different letters between "abc" and "abx" are c and x, so c must come before x. The letters a and b also appear and must be included. Among all valid orders, using normal lowercase English lexicographical order, "abcx" is lexicographically smallest.
Example 3
Input: alienOrder(words = ["abc","ab"])
Output: ""
Explanation: The word "ab" is a prefix of "abc", but the longer word appears first. This is invalid, so the result is an empty string.
Example 4
Input: alienOrder(words = ["za","zb","ca","cb"])
Output: "abzc"
Explanation: Comparing adjacent words gives a before b and z before c. The valid order must include all unique letters a, b, z, and c. Among all valid orders, using normal lowercase English lexicographical order, "abzc" is lexicographically smallest.