Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Alien Dictionary

Hard Acceptance 47.81% Points 40

You are given a sorted dictionary of an alien language containing several words (dict) and k starting alphabets of the standard dictionary. Your task is to determine the order of characters in the alien language based on the given words. If no valid ordering of characters is possible, return an empty string.

Note: Multiple valid orders may exist for a given test case. The output will be considered correct if the returned order satisfies the conditions, otherwise, the output will be "false."

Examples
Example 1

Example 1

Input: dict[] = ["caa", "aaa", "aab"], k = 3

Output: true

Explanation: The order of characters is 'c', 'a', 'b'. "caa" comes before "aaa", so 'c' is before 'a'. "aaa" comes before "aab", so 'a' is before 'b'.

Example 2

Example 2

Input: dict[] = ["z", "x", "z"], k = 2

Output: false

Explanation: No valid ordering is possible because "z" appears before and after "x," causing a contradiction.

Constraints
  • 1 <= dict.size() <= 10^4
  • 1 <= k <= 26
  • 1 <= Length of words <= 50
Hints
  • Expected Time Complexity: O(n * |s| + k)
  • ExpectedAuxiliary Space: O(k)
Topics
String
Companies
Amazon Microsoft Walmart Google Flipkart
Added 11 Apr 2025 47.81% acceptance
Ln 1, Col 1Sign in to save your code
caa aaa aab
3
true