Alien Dictionary
HardGiven a list of words sorted lexicographically in an unknown language, determine the order of characters in the alphabet of that language. If no valid ordering exists, return an empty string.
Example:
Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf" Explanation: The order of letters is "w -> e -> r -> t -> f". Input: words = ["z","x","z"] Output: "" Explanation: There is a cycle (z -> x -> z), so no valid ordering exists.
Test Cases
Test Cases
Input
wrt wrf er ett rftt
Expected Output
wertf
Step 1
Step 2
Step 3
Step 4
Step 1: Identify the Pattern
Alien Dictionary
HardGiven a list of words sorted lexicographically in an unknown language, determine the order of characters in the alphabet of that language. If no valid ordering exists, return an empty string.
Example:
Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf" Explanation: The order of letters is "w -> e -> r -> t -> f". Input: words = ["z","x","z"] Output: "" Explanation: There is a cycle (z -> x -> z), so no valid ordering exists.
Test Cases
Test Cases
Input
wrt wrf er ett rftt
Expected Output
wertf
Step 1
Step 2
Step 3
Step 4
Step 1: Identify the Pattern