Alien Dictionary

**Problem Statement:** Given the required input arguments, write an efficient algorithm to solve the **Alien Dictionary** problem. Implement the required logic as specified by standard definitions for this classic algorithmic challenge. **Hint / Expected Approach:** Build order-graph from adjacent word diffs + topo sort **Edge Cases to Consider:** - (1) Cyclic order (invalid) - (2) All same characters - (3) Prefix word after longer word (invalid)

Examples

Example 1

Input: ["wrt","wrf","er","ett","rftt"]

Output: "wertf"

Explanation: Classic

Example 2

Input: ["z","x"]

Output: "zx"

Explanation: Simple 2-char

Example 3

Input: ["z","x","z"]

Output: ""

Explanation: Cycle (invalid)

Constraints

▪2 <= vertices <= 1000
▪0 <= edges <= 5000
▪Avoid infinite cycles during depth traversal

Watch Out For Edge Cases

▪Cyclic order (invalid)
▪All same characters
▪Prefix word after longer word (invalid)

Frequently Asked At

AmazonGoogleMicrosoftMetaFlipkart

Back to Arena

hard

Graph