The input words are sorted according to an unknown alphabet. Compare adjacent words and use the first different character to learn which letter must come before another.
All distinct letters seen in the input must appear in the returned order. If the ordering rules contain a cycle, or a longer word appears before its own prefix, return an empty string.
Examples
Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"
Input: words = ["z","x"] Output: "zx"
Constraints
- 1 <= words.length <= 100
- 1 <= words[i].length <= 100