Alien Dictionary — C# Coding Problem
Difficulty: hard | Category: graph
Problem Description
You are given a list of words from an alien language dictionary, where the words are sorted lexicographically by the rules of that language. Derive the order of characters in the alien alphabet. Return a string of the unique characters in the correct order. If the order is invalid (circular dependency), return an empty string `""`. If multiple valid orderings exist, return any of them. **Hint:** Build a directed graph from adjacent word pairs and topological sort.
Examples
Example 1
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Example 2
Input: words = ["z","x"]
Output: "zx"
Example 3
Input: words = ["z","x","z"]
Output: ""
Explanation: Circular dependency — invalid order.