64. Alien Dictionary
Given a sorted dictionary of an alien language having N words and K starting alphabets of a standard dictionary. Find the order of characters in the alien language.
There may be multiple valid orders for a particular test case, thus you may return any valid order as a string. The output will be True if the order returned by the function is correct, else False denoting an incorrect order. If the given arrangement of words is inconsistent with any possible letter ordering, return an empty string "".
Example 1:
Input: N = 5, K = 4, dict = ["baa","abcd","abca","cab","cad"]
Output: b d a c
Explanation:Â
Compare every pair of consecutive words and consider only their first differing characters:
- "baa" and "abcd" first differ at index 0: b vs. a. Since "baa" appears first, b must come before a.
- "abcd" and "abca" first differ at index 3: d vs. a. Therefore, d must come before a.
- "abca" and "cab" first differ at index 0: a vs. c. Therefore, a must come before c.
- "cab" and "cad" first differ at index 2: b vs. d. Therefore, b must come before d.
These constraints produce the valid ordering [b, d, a, c].
Example 2:
Input: N = 3, K = 3, dict = ["caa","aaa","aab"]
Output: c a b
Explanation: Similarly, if we analyze the consecutive pairÂ
for this example, we will figure out [‘c’, ‘a’, ‘b’] isÂ
a valid ordering.
Now Your Turn!
Pick the correct output for the given inputInput: N = 3, K = 3, dict = ["abc", "bca", "cab"]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 ≤ N ≤ 300
- 1 ≤ K ≤ 26
- 1 ≤ dict[i].length ≤ 50