Alien Dictionary

Hard

Topological Sort

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Derive the order of letters in this language, and return it. If the order is invalid, return an empty string. If there are multiple valid orderings of letters, return any of them.

The insight: When comparing adjacent words, the first differing character tells us about letter ordering. If word1[i] != word2[i], then word1[i] comes before word2[i] in the alien alphabet. This gives us directed edges in a graph.

Real-world analogy: Imagine you're an archaeologist who discovered tablets with words in an unknown ancient language. The tablets are known to be in alphabetical order. By comparing adjacent words, you can deduce the ordering of their alphabet.

Example 1

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

Output: "wertf"

Explanation: From "wrt" and "wrf", we know t < f. From "wrt" and "er", we know w < e. From "er" and "ett", we know r < t. From "ett" and "rftt", we know e < r. The valid order is: w < e < r < t < f.

Example 2

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

Output: "zx"

Explanation: From "z" and "x", we know z < x.

Example 3

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

Output: ""

Explanation: The order is invalid. We have z < x from the first two words, but x < z from the last two, creating a contradiction.

Constraints

•1 <= words.length <= 100
•1 <= words[i].length <= 100
•words[i] consists of only lowercase English letters

Show Hints (7)

Hint 1: First, extract all the ordering relationships from adjacent word pairs.

Hint 2: How do you compare two adjacent words to find the relationship?

Hint 3: Compare character by character. The first difference gives you an edge in the graph.

Hint 4: Watch out for invalid cases: if word1 is a prefix of word2 but comes after it, that is invalid.

Hint 5: Once you have all edges, what algorithm gives you the character ordering?

Hint 6: Topological sort! Each character is a node, each ordering relationship is a directed edge.

Hint 7: If there is a cycle in the graph, return empty string (invalid ordering).

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?