Alien Dictionary

There is a new alien language which uses the Latin alphabet. The order among letters is unknown to you. You receive a list of non-empty words from this language, **sorted lexicographically** according to alien rules. Derive a possible character order of the language. Return any valid ordering of characters in the alien language. If the ordering is invalid or cannot be determined, return an empty string. **Notes:** - You may assume all letters are lowercase. - If `a` is a prefix of `b`, then `a` must come before `b` in the input list. - If the order is invalid (e.g. contradicting rules), return `""`. - If multiple valid orders exist, return any. **Example 1:** Input: ["wrt","wrf","er","ett","rftt"] Output: "wertf" **Example 2:** Input: ["z","x"] Output: "zx" **Example 3:** Input: ["z","x","z"] Output: "" (invalid ordering)