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."
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
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.
Approach, complexity and clean code in every language. Sign in to unlock the editorial.
Your submissions, results and runtime history live here. Sign in to start your streak.
caa aaa aab 3
true
z x z 2
false