Practice/Google/Leetcode 269. Alien Dictionary

Leetcode 269. Alien Dictionary

CodingMust

Problem

You are given a list of words from an ancient alien language that uses characters similar to English but with a completely different alphabetical ordering. The words are sorted lexicographically according to the alien language's character ordering rules.

Your task is to determine the order of characters in this alien alphabet. If multiple valid orderings exist, return any one of them. If no valid ordering exists (due to contradictions or invalid input), return an empty string.

Requirements

1. Derive character precedence rules by comparing consecutive words in the list
2. Build a directed graph where an edge from character A to character B means A comes before B in the alien alphabet
3. Perform topological sorting on this graph to determine a valid character ordering
4. Detect cycles (contradictory ordering constraints) and return empty string if found
5. Detect invalid prefix violations (longer word appearing before its prefix) and return empty string
6. Include all characters that appear in the input words in your result

Constraints

• 1 ≤ words.length ≤ 100
• 1 ≤ words[i].length ≤ 100
• words[i] consists of lowercase English letters only
• You must solve this in O(C) time where C is the total number of characters across all words
• If multiple valid orderings exist, return any valid one

Examples

Example 1:

` Input: words = ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf" Explanation:

• Comparing "wrt" and "wrf": t comes before f
• Comparing "wrf" and "er": w comes before e
• Comparing "er" and "ett": r comes before t
• Comparing "ett" and "rftt": e comes before r
• Final ordering: w → e → r → t → f `

Example 2:

Input: words = ["z", "x"] Output: "zx" Explanation: From the ordering, z must come before x in the alien alphabet.

Example 3:

Input: words = ["abc", "bca", "cab"] Output: "" Explanation: This input creates a cycle (a<b, b<c, c<a), so no valid ordering exists.

Example 4:

Input: words = ["monster", "mon"] Output: "" Explanation: Invalid because "mon" is a prefix of "monster" but appears after it, violating lexicographic ordering.