696. Unknown Alphabet
Explorers found a dictionary written in an unknown alphabet that uses only lowercase English letters, though in some hidden order. The list words is claimed to be sorted in ascending order under that alphabet, using the usual dictionary rule: compare two words at the first position where they differ, and a word that is a proper prefix of another one comes first.
Return a string containing every letter that appears in words exactly once, arranged so that the list is correctly sorted. Any valid arrangement is accepted. If no arrangement can make the list sorted (the words contradict each other, or a longer word is followed by its own prefix), return an empty string.
Aim for time linear in the total number of characters.
Example 1
- Input:
- words = ["zx","zy","xy"]
- Output:
- "zxy"
- Explanation:
zx before zy gives x before y, and zy before xy gives z before x; the only order is z, x, y.
Example 2
- Input:
- words = ["ab","a"]
- Output:
- ""
- Explanation:
The longer word ab is listed before its own prefix a, which no alphabet allows, so the answer is empty.
Constraints
1 ≤ words.length ≤ 20000
1 ≤ words[i].length ≤ 20 and the total number of characters is at most 100000
words[i] consists of lowercase English letters; duplicate words are allowed
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(L + A^2)
- Space
- O(A^2)